Hybrid Evolutionary Search
From CometPublic
|
[edit] What is Hybrid Evolutionary Search?
(from [CBLS])
[edit] Presentation
Hybrid evolutionary algorithms exploit the strengths of both local and evolutionary search (see genetic algorithm).
Evolutionary algorithms maintain a pool of solutions (the population) that are crossed to produce new solutions.
Before crossing them, it applies local search to the solutions in the population.
As a result, hybrid evolutionary algorithms benefit from effectiveness of local search in finding high quality solutions,
while the evolutionary aspects, the pool of solutions and the crossover operators, provide novel ways of diversifying the search escaping local minima.
Here is a basic hybrid evolutionary template:
1. function HybridLocalSearch(f, N, L, S) {
2. P := InitPopulation(f, N, L, S);
3. best := select s in P minimizing f(s);
4. for k := 1 to MaxIterations do
5. select s1, s2 in P;
6. s := Crossover (s1, s2);
7. s := LocalSearch(f, N, L, S, s);
8. if f(s) < f(best) then
9. best := s;
10. P := UpdatePopulation(s, s1, s2, P);
11. return best;
12.}
The algorithm starts by generating an initial population P of solutions which are obtained by (randomly) generating a solution on which local search is applied. The core of the algorithm selects two solutions (the parents) from the population (line 5), crosses them to obtain a new solution s (line 6), applies local search to find an improved solution (line 7) and updates the population using s and its parents (line 10). The population is updated by inserting s if it improves upon one of the parents.
The initial solution, the local search and the crossover operator are problem-specific and exploit the structure of the application.
The hybrid evolutionary algortihm is completely separated from the local search algorithm and each component can be modified independently without affecting the other.
[edit] Issues
An important issue is to maintain the diversity of the population in order to keep generating sufficiently different starting points as the search progresses.
Another important issue is the methodology of designing effective crossover operators.
[edit] Using hybrid evolutionnary search into Langford's number problem
The following sections describe the problem and explain the main features of the algorithm.
[edit] Description of the problem
The Langford's number problem is introduced here: http://www.dcs.st-and.ac.uk/~ianm/CSPLib/prob/prob024/spec.html and here: http://www.lclark.edu/~miller/langford.html.
[edit] Implementation in Comet
The code of the implementation of the Langford's numbers problem with the hybrid evolutionary search can be found here: langfordHES.co.
It is based on the generic implementation that you can find in [CBLS](chap14) and in the Comet Web Site library.
[edit] Model
[edit] Decision variables
The algorithm needs two parameters:
- S: number of sets;
- N: maximal limit of the set (1 to N).
To store the sequence of N*S numbers, the algorithm uses a matrix[S,N] of S rows and N columns representing the sequence.
Here is an example with S = 2 and N = 4:
| S/N | 1 | 2 | 3 | 4 |
| 1 | 2 | 5 | 3 | 1 |
| 2 | 4 | 8 | 7 | 6 |
represents
| 4 | 1 | 3 | 1 | 2 | 4 | 3 | 2 |
Column 1 of the matrix represents the position of number 1 in the sequence: it is in position 2 and 4.
Column 2 of the matrix represents the position of number 2 in the sequence: it is in position 5 and 8.
...
Column x of the matrix represents the position of number x in the sequence: it is in position Matrix[1,x] and Matrix[2,x].
[edit] Constraints
There are 2 constraints :
- alldifferent constraint: all the numbers in the matrix must be different: the positions of the numbers must be in 1..N*S and each number has only one position in the sequence. Since the algorithm work with a permutation of the numbers (1..N*S) in the matrix and only swap numbers of two cells, this constraint is useless because it is always maintained by the algorithm. But leaving this constraint in the constraints system improves the local search.
- distance constraints:
CS = new ConstraintSystem(mgr);
forall(l in 2..S, k in Numbers)
{
CS.post(abs(Mat[l,k] - Mat[l-1,k]) == k + 1);
}
| 3 |
| 3 |
| 7 |
In this example above (showing the third column of the matrix above), 7 - 3 must be equal to 3 + 1.
The total violation is the sum of each column violation.
[edit] Local search
The core of the search is a greedy local search algorithm that selects two different cells from the matrix of a solution and swap them to minimize the violation.
it = 0;
best = violations;
sol = new Solution(mgr,best);
while (violations > 0 && it < itLimit) {
int old = violations;
int gap = best - violations;
selectMin(l1 in Series,l2 in Series, k1 in Numbers,k2 in Numbers , delta = CS.getSwapDelta(Mat[l1,k1],Mat[l2,k2]): (l1 != l2 || k1 != k2)&&
delta < gap)(delta) {
Mat[l1,k1] :=: Mat[l2,k2];
}
if (violations <= best) {
best = violations;
sol = new Solution(mgr,best);
}
it++;
}
[edit] Crossover operator
The crossover operator simply receives two parents and combines them to create a child, which is a new solution (with violated constraints or not).
- The MatPos matrix (line 3) stores the indices of the cells of the child's matrix that have not received a value.
- The count (line 4) is used with the modulo operator to select a number once from parent a, once from parent b.
- For each c in Domain (each number in N*S) (line 5), the algorithm gets the position of the number c in the parent and assigns it to the same position in the child's matrix, if this position has not yet received a value (line 9-14 & 26-31). Otherwise the algorithm (randomly) selects another free position in the child and assigns the number c to this position (line 15-21 & 32-38).
1. void crossover(Solution a,Solution b) {
2. with atomic(mgr) {
3. int MatPos[Series,Numbers] = 0;
4. int count = 0;
5. forall(c in Domain)
6. {
7. if (count%2 == 0)
8. {
9. select(s in Series, n in Numbers : Mat[s,n].getSnapshot(a) == c){
10. if (MatPos[s,n] == 0)
11. {
12. MatPos[s,n] = 1;
13. Mat[s,n] := c;
14. }
15. else
16. {
17. select(k in Series, l in Numbers : MatPos[k,l] == 0){
18. MatPos[k,l] = 1;
19. Mat[k,l] := c;
20. }
21. }
22. }
23. }
24. else
25. {
26. select(s in Series, n in Numbers : Mat[s,n].getSnapshot(b) == c){
27. if (MatPos[s,n] == 0)
28. {
29. MatPos[s,n] = 1;
30. Mat[s,n] := c;
31. }
32. else
33. {
34. select(k in Series, l in Numbers : MatPos[k,l] == 0){
35. MatPos[k,l] = 1;
36. Mat[k,l] := c;
37. }
38. }
39. }
40. }
41. count++; //end of forall
42. }
43. }
44. }
[edit] Results
These tables compare the results from the hybrid evolutionary search (HES) and the "simple" greedy search (GREEDY) (without HES) for 20 runs of each.
| S | m(V) | M(V) | mean(V) | m(I) | M(I) | mean(I) | m(T) | M(T) | mean(T) | |
|---|---|---|---|---|---|---|---|---|---|---|
| HES | 85%(17) | 0 | 2 | 0.3 | 38 | 336 | 120.9 | 14 | 103 | 38.65 |
| GREEDY | 100%(20) | 0 | 0 | 0 | 2 | 87 | 14.7 | 0 | 40 | 6.8 |
| S | m(V) | M(V) | mean(V) | m(T) | M(T) | mean(T) | |
|---|---|---|---|---|---|---|---|
| HES | 0%(0) | 3 | 6 | 4.75 | 18000 | 18000 | 18000 |
| GREEDY | 0%(0) | 4 | 8 | 6.35 | 27400 | 29250 | 28500 |
m: minimum, M: maximum, V: # violations, I: # iterations, T: time
(In the second table, # iterations is omitted because both cases reach the maximum (I = 3186))
The results show that for small instances of the problem, the simple greedy search find always a good solution, and is in this case better and faster than hybrid evolutionary search.
For bigger instances of the problem, hybrid evolutionary search and simple greedy search didn't find any good solution. But we observe that hybrid evolutionay search gives a better local optimum with less violations than simple greedy search.
[edit] Improvements (to do)
- improve the local search;
- improve the selection of the two parents and find a better crossover operator.
[edit] References
- [CBLS] P. Van Hentenryck, L. Michel (2005) Constraint-Based Local Search. MIT Press, Cambridge, London.
- Langford's number problem (1)
- Langford's number problem (2)
