-
Notifications
You must be signed in to change notification settings - Fork 1
/
Crossover.java
210 lines (198 loc) · 11.3 KB
/
Crossover.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
import java.util.LinkedList;
import java.util.Map;
import java.util.Random;
import java.util.Vector;
/**
* Crossover
*/
public class Crossover {
/**
* OnePoint - randomowo wybierany jest pojedynczy crosspoint dla obojgu rodziców.
* Pierwsze dziecko jest kolorowana przed crosspointem takimi samymi kolorami jak rodzic A miał przed nim,
* a reszta wierzchołków jest kolorowana tamiki samymi kolorami jak rodzic B miał po crosspoincie.
* Kolejne dziecko jest kolorowane odwrotnie, na początku ma kolory rodzica B, a potem kolory od rodzica A.
* Połowa dzieci w populacji ma taki sam kolor.
* @param parents element mapy(watość,klucz) zawierający dwa chromosomy - rodziców
* @param population wektor chromosomów (wektorów wierzchołków)
* @return population - nowa populacja po zamianie kolorów
*/
public static Vector<Vector<Vertex>> onePoint(Map.Entry<Vector<Vertex>, Vector<Vertex>> parents, Vector<Vector<Vertex>> population) {
int crosspoint = new Random().nextInt(population.get(1).size()); //A - generowanie losowej liczby crosspoint z ilości wierzchołków w chromosomie
for (int j = 0; j < population.size(); j++) {
int probability = new Random().nextInt(100);
if (probability < 70) {
Vector<Vertex> child = population.get(j); //A - child - jeden chromosom z populacji Offspring
switch (j % 2) {
case 0: //kolorowanie dwójki dzieci tak samo
for (int i = 0; i < child.size(); i++) { //przejście i odpowiednie ustawienie kolorów wierzchołków w dziecku
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i); //temp - jeden wierzchołek dziecka
int newId = temp.id; //id danego wierzchołka dziecka, któremu zmieni się odpowiednio kolor
if (newId < crosspoint) { //kolorowanie przed crosspointem
temp.kolor = kolor1;
} else { //kolorowanie po crosspoincie
temp.kolor = kolor2;
}
child.set(i, temp);
}
population.set(j, child);
break;
case 1: //kolorowanie dwójki dzieci odwrotnie do poprzedniego
for (int i = 0; i < child.size(); i++) { //przejście i odpowiednie ustawienie kolorów wierzchołków w dziecku
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i); //temp - jeden wierzchołek z wybranego dziecka
int newId = temp.id;
if (newId < crosspoint) {
temp.kolor = kolor2;
} else {
temp.kolor = kolor1;
}
child.set(i, temp);
}
population.set(j, child);
break;
}
}
}
return population;
}
/**
* twoPoint - wybieramy randomowo dwa crosspointy.
* Pierwsze dziecko jest kolorowane do pierwszego crosspointa kolorami rodzica A,
* między pierwszym a drugim crosspointem kolorami rodzica B,
* po drugim kolorami rodzica A.
* Kolejne dziecko odwrotnie, na początku kolory od rodzica B, potem A, potem znowu B.
* Połowa dzieci w populacji ma taki sam kolor.
*
* @param parents element mapy(watość,klucz) zawierający dwa chromosomy - rodziców
* @param population wektor chromosomów (wektorów wierzchołków)
* @return population - nowa populacja po zamianie kolorów
*/
public static Vector<Vector<Vertex>> twoPoint(Map.Entry<Vector<Vertex>, Vector<Vertex>> parents, Vector<Vector<Vertex>> population) {
int chromosomSize = population.elementAt(1).size();
int crosspoint1 = new Random().nextInt(chromosomSize);
int crosspoint2;
do {
crosspoint2 = new Random().nextInt(chromosomSize);
} while (crosspoint1 >= crosspoint2); //A - ustawianie crosspoint1 na mniejszy, a crosspoint2 na większy
for (int j = 0; j < population.size(); j++) {
int probability = new Random().nextInt(100);
if (probability < 70) {
Vector<Vertex> child = population.get(j); //A - child - jeden chromosom z populacji Offspring
switch (j % 2) {
case 0: //kolorowanie dwójki dzieci tak samo
for (int i = 0; i < child.size(); i++) { //przejście i odpowiednie ustawienie kolorów wierzchołków w dziecku
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i); //temp - jeden wierzchołek dziecka
int newId = temp.id; //id danego wierzchołka dziecka, któremu zmieni się odpowiednio kolor
if (newId < crosspoint1 || newId > crosspoint2) {
temp.kolor = kolor1;
} else {
temp.kolor = kolor2;
}
child.set(i, temp);
}
population.set(j, child);
break;
case 1: //kolorowanie dwójki dzieci tak samo
for (int i = 0; i < child.size(); i++) { //przejście i odpowiednie ustawienie kolorów wierzchołków w dziecku
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i); //temp - jeden wierzchołek dziecka
int newId = temp.id; //id danego wierzchołka dziecka, któremu zmieni się odpowiednio kolor
if (newId < crosspoint1 || newId > crosspoint2) {
temp.kolor = kolor2;
} else {
temp.kolor = kolor1;
}
child.set(i, temp);
}
population.set(j, child);
break;
}
}
}
return population;
}
/**
* Uniform - kolory są randomowo kopiowane albo od rodzica A, albo od rodzica B.
* @param parents element mapy(watość,klucz) zawierający dwa chromosomy - rodziców
* @param population wektor chromosomów (wektorów wierzchołków)
* @return population - nowa populacja po zamianie kolorów
*/
public static Vector<Vector<Vertex>> uniform(Map.Entry<Vector<Vertex>, Vector<Vertex>> parents, Vector<Vector<Vertex>> population) {
for (int j = 0; j < population.size(); j++) {
int probability = new Random().nextInt(100);
if (probability < 70) {
Vector<Vertex> child = population.get(j); //A - child - jeden chromosom z populacji Offspring
switch (j % 2) {
case 0: //kolorowanie dwójki dzieci tak samo
for (int i = 0; i < child.size(); i++) {
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i);
Random generator = new Random();
switch (generator.nextInt(2)) { //A - randomowe wybieranie koloru jednego z dwóch
case 0:
temp.kolor = kolor1;
break;
case 1:
temp.kolor = kolor2;
break;
}
child.set(i, temp);
}
population.set(j, child);
break;
case 1: //kolorowanie dwójki dzieci tak samo
for (int i = 0; i < child.size(); i++) {
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i);
Random generator = new Random();
switch (generator.nextInt(2)) { //A - randomowe wybieranie koloru jednego z dwóch
case 0:
temp.kolor = kolor2;
break;
case 1:
temp.kolor = kolor1;
break;
}
child.set(i, temp);
}
population.set(j, child);
break;
}
}
}
return population;
}
/**
* Arithmetic - populacja jest tworzona przez arytmetyczne działania na kolorach rodziców.
* Działanie - iloczyn kolorów rodziców modulo ilość kolorów występujących w danym grafie.
* @param parents element mapy(watość,klucz) zawierający dwa chromosomy - rodziców
* @param population wektor chromosomów (wektorów wierzchołków)
* @param colors - ilość kolorów występujących w danym grafie
* @return population - nowa populacja po zamianie kolorów
*/
public static Vector<Vector<Vertex>> arithmetic(Map.Entry<Vector<Vertex>, Vector<Vertex>> parents, Vector<Vector<Vertex>> population, int colors) {
for (int j = 0; j < population.size(); j++) {
int probability = new Random().nextInt(100);
if (probability < 70) {
Vector<Vertex> child = population.get(j); //A - child - jeden chromosom z populacji Offspring
for (int i = 0; i < child.size(); i++) {
int kolor1 = parents.getKey().get(i).kolor; //kolor1 = kolor z pierwszego parenta
int kolor2 = parents.getValue().get(i).kolor; //kolor2 = kolor z drugiego parenta
Vertex temp = child.get(i);
temp.kolor = (kolor1 * kolor2) % colors; //modulo ilość kolorów występujących w danym grafie
child.set(i, temp);
}
population.set(j, child);
}
}
return population;
}
}