 |
|
Classical optimization algorithms such as sequential quadratic programming (SQP) need at least a feasible point to start with because they are not usually able to jump out of unfeasible areas. When a problem is strongly constrained it can be more complex to find the initial point than to proceed with the classical gradient based optimization.
With stochastic optimization algorithms, such as Genetic Algorithms or Evolutionary Strategies, the feasibility of the initial points is not moreover necessary. but obviously appreciated.
The goal of the constraint satisfaction problem is to find an assignment to each variable so that all constraints are satisfied. Higly constrained problems can be really difficult and algorithms often take an unacceptably long time to solve these problems exactly. A large number of different approaches have been developed for providing a solution to these types of problem. The simplest possibility is the brute force approach of complete enumeration that searches systematically through all the possible assignments of values to variables. Such algorithms guarantee a solution if it exists (or they prove that the problem is insoluble) but this approach is obviously very heavy and may take a very long time. Even with the increasing computing power, the combinatorial explosion limits the size of the problems solvable with the complete enumeration method. Some algorithms use backtracking to directly search for possible solutions, others try to simplify the original problem, some other are hybrid methods, combination of different techniques. This algorithm uses an heuristic approach for constraint satisfaction problems (CSPs). Heuristic algorithms cannot guarantee the best solution will be reached but are used to produce good solutions in a reasonable amount of time.
In this algorithm, a modified simulated annealing is used in search for feasible designs. The designs are constructed using record-to-record travel (RRT). In RRT every move that gives a new solution that is "not much worse" than the best value found so far (the record) is always accepted. The maximum allowed deviation determines how much worse values than the current record are accepted.
In spite of its simplicity, this algorithm shows to be the fastest algorithm in converging towards the feasible region with respect to other more complex tools present in literature. Moreover, it has demonstrated to correctly work both with continuous and discrete problems, to manage problems with both few and many variables and to handle several types of constraints. For this reason we can say that this algorithm has shown to be really problem independent.
A better description of the algorithm is available in the paper Constraint Satisfaction Problem using Record-to-Record Travel.
Some parameters must be defined:
Number of Iterations a positive integer number between 1 and the maximum number of iterations (i.e. 9999). The number of iterations is directly connected with the time that the algorithm takes to produce a good solution; the greater it is, the better the algorithm performs, because both the robustness and the convergence are improved. The obvious drawback is the greater computational requests.
Allowed Deviation a value that determines how much worse values than the current record are accepted. This is the most important parameter for the algorithm. Selecting a small deviation, the algorithm is not able to find a solution. This behavior is quite reasonable since algorithm will not be able to escape from local optimum. So, lower values imply a greater convergence, but the price to pay is a loss in the algorithm's robustness. Alternatively, by choosing a large deviation, a feasible solution is slowly generated. If the deviation is large enough the algorithm is effectively performing a random search over the entire solution space. When the deviation is high, almost all unfavorable perturbations are accepted, and the algorithm does not seem in this case to converge in any sense to a feasible solution. So, higher values imply a greater robustness but so a lot of time is spent before the algorithm converges. Obviously the effectively the maximum value for the allowed deviation is equal to the number of constraints. The job then lies in finding the appropriate values for the deviation parameter mediating between speed and quality of solutions. The exact value will obviously depends on the specific problem under consideration. Several suggestions can be given concerning the selection of the appropriate deviation value: for the constraint satisfaction problems, the deviation parameter should be consider as a percentage of the total number of constraints. Many practical examples showed that a good choice can be between 15% and 20%, this value represents a good compromise between robustness and convergence.
Initial Perturbation this value determines the spread of points distribution in variables space. Higher values increase the algorithm robustness, being possible to explore the space beyond eventual local optima, helping the search for feasible solutions; however when this value is equal to 1 the evolution becomes totally random. On the contrary lower values imply a greater convergence; but when the value is equal to 0 the algorithm again performs bad.
Minimum Perturbation Length this value determines the minimum spread of points distribution in variables space.
Random Generator Seed A positive integer number, used for sequence repeatability. If two Random Sequences are created with the same seed, they will generate and return identical sequences of numbers. If the seed value is 0, the sequence is automatically seeded to a value based on the current time.
