Проверила

Мухлаева И. В.

Москва 2013

1) Текст задания

Построить генетический алгоритм для решения задачи о коммивояжере.

2) Описание алгоритма

3) Использованные операторы

При выполнении данного алгоритма использовались следующие операторы:

а) Кроссовера

- Упорядочивающий

- Жадный

Далее сравниваются результаты этих операторов кроссовера.

б) Мутации

- Обмена

в) Селекции

- Случайная

Фитнесс функция определяется как

fitfun = sum(a[i] * 2), если i – четный индекс символа, а[i] – само числовое значение индекса

4) Статистические исследования алгоритма

При работе программы использовались следующие параметры:

- Размер начальной популяции – 10 особей

- Размер хромосомы – 8 бит

- Вероятность мутации – 0,2

- Вероятность кроссовера – 0,2 – 0,9 с шагом 0,1

- Число генераций – 6

ОК\Вер-ть ОК	0,2	0,3	0,4	0,5	0,6	0,7	0,8	0,9	Среднее
Упорядочивающий									36,214
Жадный									35,857

Оценивая средние значения, можно сделать вывод, что упорядочивающий оператор кроссинговера приводит к более качественному новому поколению, чем жадный ОК.

Генерация
Упоряд. макс
Жадный макс
Упоряд. сред.
Жадный сред

5) Текст программы

Упорядочивающий ОК

private void Cross_Mode1(int[] P1, int[] P2, List<string> lst)

{

Random rand = new Random();

int[] O1 = new int[chr_length];

int[] O2 = new int[chr_length];

int Point1 = rand.Next(1, chr_length);

for (int i = 0; i < Point1; i++)

{

O1[i] = P1[i];

O2[i] = P2[i];

}

for (int i = Point1; i < chr_length; i++)

{

for (int j = 0; j < chr_length; j++)

if (!O1.Contains(P2[j]))

{

O1[i] = P2[j];

break;

}

for (int j = 0; j < chr_length; j++)

if (!O2.Contains(P1[j]))

{

O2[i] = P1[j];

break;

}

}

string str = "";

for (int i = 0; i < chr_length; i++)

str += O1[i];

lst.Add(str);

}

Жадный ОК

private void Cross_Mode2(int[] P1, int[] P2, List<string> lst)

{

Random rand = new Random();

int[] O1 = new int[chr_length];

int[] O2 = new int[chr_length];

int a = rand.Next(0, chr_length);

for (int i = 0; i < chr_length; i++)

{

O1[i] = -1;

O2[i] = -1;

}

O1[0] = a;

int counter = 1;

int st1 = 0;

int st2 = 0;

for (int i = 0; i < chr_length; i++)

{

if (P1[i] == a)

st1 = i;

if (P2[i] == a)

st2 = i;

}

while (counter < chr_length)

if (st1!= chr_length - 1 && st2!= chr_length - 1)

if (matr[P1[st1],P1[st1 + 1]] < matr[P2[st2],P2[st2 + 1]])

if (!O1.Contains(P1[st1 + 1]))

{

a = P1[++st1];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O1.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O1.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O1.Contains(P1[st1 + 1]))

{

a = P1[++st1];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

else

if (st1 == chr_length - 1 && st2 == chr_length - 1)

if (matr[P1[st1],P1[0]] < matr[P2[st2],P2[0]])

if (!O1.Contains(P1[0]))

{

a = P1[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O1.Contains(P2[0]))

{

a = P2[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O1.Contains(P2[0]))

{

a = P2[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O1.Contains(P1[0]))

{

matr[P1[st1],P1[0]] = 0;

a = P1[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

else

if (st1 == chr_length - 1)

if (matr[P1[st1],P1[0]] < matr[P2[st2],P2[st2 + 1]])

if (!O1.Contains(P1[0]))

{

a = P1[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O1.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O1.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O1.Contains(P1[0]))

{

matr[P1[st1],P2[0]] = 0;

a = P1[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

else

if (matr[P1[st1],P1[st1 + 1]] < matr[P2[st2],P2[0]])

if (!O1.Contains(P1[st1 + 1]))

{

a = P1[++st1];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O1.Contains(P2[0]))

{

a = P2[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O1.Contains(P2[0]))

{

a = P2[0];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O1.Contains(P1[st1 + 1]))

{

matr[P1[st1],P1[st1 + 1]] = 0;

a = P1[++st1];

O1[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

a = rand.Next(0, chr_length);

O2[0] = a;

counter = 1;

for (int i = 0; i < chr_length; i++)

{

if (P1[i] == a)

st1 = i;

if (P2[i] == a)

st2 = i;

}

while (counter < chr_length)

if (st1!= chr_length - 1 && st2!= chr_length - 1)

if (matr[P1[st1],P1[st1 + 1]] < matr[P2[st2],P2[st2 + 1]])

if (!O2.Contains(P1[st1 + 1]))

{

a = P1[++st1];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O2.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O2.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O2.Contains(P1[st1 + 1]))

{

a = P1[++st1];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

else

if (st1 == chr_length - 1 && st2 == chr_length - 1)

if (matr[P1[st1],P1[0]] < matr[P2[st2],P2[0]])

if (!O2.Contains(P1[0]))

{

a = P1[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O2.Contains(P2[0]))

{

a = P2[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O2.Contains(P2[0]))

{

a = P2[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O2.Contains(P1[0]))

{

matr[P1[st1],P1[0]] = 0;

a = P1[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

else

if (st1 == chr_length - 1)

if (matr[P1[st1],P1[0]] < matr[P2[st2],P2[st2 + 1]])

if (!O2.Contains(P1[0]))

{

a = P1[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O2.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O2.Contains(P2[st2 + 1]))

{

a = P2[++st2];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O2.Contains(P1[0]))

{

matr[P1[st1],P2[0]] = 0;

a = P1[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

else

if (matr[P1[st1],P1[st1 + 1]] < matr[P2[st2],P2[0]])

if (!O2.Contains(P1[st1 + 1]))

{

a = P1[++st1];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

if (!O2.Contains(P2[0]))

{

a = P2[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

return;

else

if (!O2.Contains(P2[0]))

{

a = P2[0];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P1[i] == a)

st1 = i;

}

else

if (!O2.Contains(P1[st1 + 1]))

{

matr[P1[st1],P1[st1 + 1]] = 0;

a = P1[++st1];

O2[counter++] = a;

for (int i = 0; i < chr_length; i++)

if (P2[i] == a)

st2 = i;

}

else

return;

string str = "";

for (int i = 0; i < chr_length; i++)

str += O1[i];

lst.Add(str);

}

Мутация обмена

private void Mutation(int[] P, List<string> lst)

{

Random rand = new Random();

int[] O = new int[P.Length];

for (int i = 0; i < chr_length; i++)

O[i] = P[i];

int point = rand.Next(1, chr_length);

if (point == chr_length - 1)

{

int q = O[point - 1];

O[point - 1] = P[point];

O[point] = q;

}

else

{

int q = O[point];

O[point] = O[point + 1];

O[point + 1] = q;

}

string str = "";

for (int i = 0; i < chr_length; i++)

str += O[i];

lst.Add(str);

}

Случайная селекция

private void Selection(string str, int r, List<string> lst)

{

if (r == 1)

lst.Add(str);

}

6) Интерфейс программного окна

Дата добавления: 2015-04-24