Оптимизация структуры распределённого параллельного генетического алгоритма

1. Обзор предметной области

2. Постановка задачи

3. Описание используемых алгоритмов

3.1 Генетическое представление задачи

3.2 Наброс

3.3 Вычисление функции приспособленности

3.4 Наброс

3.5. Группировка в подпопуляции

3.6 Условие окончания счёта

3.7 Скрещивание

3.8 Мутация

4. Программная реализация

4.1 Схема программного обеспечения

4.2 Описание основных методов

4.4 Тестирование и руководство пользователя Заключение Литература Приложение

Существуют задачи, для которых доказано отсутствие общего алгоритма решения (например, задача о разрешимости Диофантова множества). В то же время, можно сказать, что, если обладать бесконечным запасом времени и соответствующими ресурсами, то можно найти решение любой задачи. Здесь имеется в виду не конструирование нового знания на основании имеющегося (вывод новых теорем из аксиом и уже выведенных теорем), а, прежде всего, перебор вариантов.

Еще в XVII столетии великий Лейбниц пытался раскрыть тайну «Всеобщего Искусства Изобретения». Он утверждал, что одной из двух частей этого искусства является комбинаторика — перебор постепенно усложняющихся комбинаций исходных данных. Второй частью является эвристика — свойство догадки человека. И сейчас вторая часть Искусства Изобретения все еще остается нераскрытой. На языке нашего времени эта часть — модель мышления человека, включающая в себя процессы генерации эвристик (догадок, изобретений, открытий).

Для решения таких задач применяются эволюционные алгоритмы. Они находят огромное применение в современной науке и технике, и показывают подчас просто поразительные результаты.

Основные принципы эволюционной теории заложил Чарльз Дарвин в своей самой революционной работе — «Происхождение видов». Самым важным его выводом был вывод об основной направляющей силе эволюции — ею признавался естественный отбор. Другими словами — выживает сильнейший (в широком смысле этого слова). Забегая вперед, замечу, что любой эволюционный алгоритм имеет такой шаг, как выделение самых сильных (полезных) особей. Вторым, не менее важным выводом Дарвина был вывод об изменчивости организмов. Аналогом данного закона у всех алгоритмов является шаг генерации новых экземпляров искомых объектов (решений, структур, особей, алгоритмов).

Именно отбор наилучших объектов является ключевой эвристикой всех эволюционных методов, позволяющих зачастую уменьшить время поиска решения на несколько порядков по сравнению со случайным поиском. Если попытаться выразить эту эвристику на естественном языке, то получим: сложно получить самое лучшее решение, модифицируя плохое. Скорее всего, оно получится из нескольких лучших на данный момент.

Из основных особенностей эволюционных алгоритмов можно отметить их некоторую сложность в плане настройки основных параметров (вырождение, либо неустойчивость решения). Поэтому, экспериментируя с ними, и получив не очень хорошие результаты, попробуйте не объявлять сразу алгоритм неподходящим, а попытаться опробовать его при других настройках. Данный недостаток следует из основной эвристики — можно «уничтожить» предка самого лучшего решения, если сделать селекцию слишком «жесткой» (не зря ведь биологам давно известно, что если осталось меньше десятка особей исчезающего вида, то этот вид сам по себе исчезнет из-за вырождения). Генетический алгоритм является самым известным на данный момент представителем эволюционных алгоритмов.

Данный курсовой проект состоит из разделов:

Раздел 1 — Обзор предметной области. Содержит описание генетических алгоритмов и алгоритмов селекции, мутации, скрещивания, применяемых для реализации генетических алгоритмов.

Раздел 2 — Постановка задачи. В данном разделе выполняется описание поставленной задачи.

Раздел 3 — Описание используемых алгоритмов. Содержит описание алгоритмов, которые применялись для решения поставленной задачи.

Раздел 4 — Программная реализация. Состоит из описания программной части, также в нём приведены диаграммы классов и их описание.

1. Обзор предметной области

Генетический алгоритм (ГА) Генетический алгоритм является самым известным на данный момент представителем эволюционных алгоритмов, и по своей сути является алгоритмом для нахождения глобального экстремума многоэкстремальной функции. ГА представляет собой модель размножения живых организмов.

В данном курсовом проекте реализована одна из модификаций ГАраспределённый параллельный генетический алгоритм.

На первом шаге алгоритма осуществляется преобразование независимых переменных в хромосомы, которые будут содержать всю необходимую информацию о каждой создаваемой особи. Имеется два варианта кодирования параметров:

· в двоичном формате;

· в формате с плавающей запятой.

В курсовом проекте используется первый вариант кодирования, в котором используется N бит для каждого параметра, причем N может быть различным для каждого параметра.

Второй шаг работы алгоритма — наброс начальной популяции хромосом. В курсовом проекте это происходит случайным образом. Далее определяется их «полезность», рассчитывая значение функции приспособленности.

Следующий ключевой шаг работы РПГА — распределение хромосом на подпопуляции: это осуществляется по значению функций приспособленности, соответствующей хромосоме.

Далее все последующие действия производятся внутри подпопуляций.

Начиная с этой точки, РПГА начинает отбор хромосом в следующее поколение.

Из первого поколения во второе переходят все хромосомы, а в последующие только небольшое количество наилучших по функции приспособленности хромосом. Это необходимо для того, чтобы популяции не разрастались.

Следующий шаг алгоритма — репродукция. Она состоит из нескольких подшагов:

· селекция;

· скрещивание;

· мутация;

Селекция — формирование пар родителей. Скрещивание — генерация новой хромосомы, объединяя генетический материал двух родительских. Существует несколько вариантов скрещивания. Наиболее простым является одноточечный. В этом варианте просто берутся две хромосомы, сформированные в результате селекции, и перерезаются в случайно выбранной точке.

Мутация представляет собой случайное изменение хромосомы (обычно простым изменением состояния одного из битов на противоположное). Данный оператор позволяет более быстро находить РПГА локальные экстремумы с одной стороны, и позволяет «перескочить» на другой локальный экстремум с другой.

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

Через некоторое количество поколений происходит обмен одной из случайных хромосом внутри подпопуляций.

В генетическом алгоритме сохраняется основной принцип естественного отбора — чем приспособленнее индивидуум (чем больше соответствующее ему значение целевой функции), тем с большей вероятностью он будет участвовать в скрещивании.

2. Постановка задачи

генетический алгоритм программный селекция

Темой курсового проекта является оптимизация структуры распределённого параллельного генетического алгоритма (РПГА). Поставленная задача сводится к созданию надстройки над реализацией генетического алгоритма, которая при помощи РПГА верхнего уровня будет оптимизировать структуру РПГА нижнего уровня.

Исследуемая функция:

Функция исследуется на минимум и максимум в области с шагом 0,1 по оси X и 0.5 по оси Y.

Исходные данные для РПГА верхнего уровня представлены в таблице 2.1.

Таблица 2.1. Исходные данные для алгоритма верхнего уровня

Исходные данные для генетического алгоритма селекционеров нижнего уровня представлены в таблице 2.2.

Таблица 2.2. Исходные данные для алгоритма нижнего уровня

Для реализации курсового проекта была разработана IDEF схема приложения рисунок 2.1(первый уровень), рисунок 2.2(второй уровень), рисунок 2.3(третий уровень).

Рисунок 2.1 IDEF схема 1-ый уровень.

3. Описание используемых алгоритмов

3.1 Генетическое представление задачи

Хромосома представляется 4 генами, первый ген кодирует начальное количество точек (0−8 точек; 1−9 точек; 2- 10 точек; 3−11 точек; 4−12 точек), следующий кодирует количество поколений (0−10 поколений; 1- 25 поколений; 2−50 поколений; 3−75 поколений; 4−100 поколений) следующий ген кодирует вид сетки (0 — треугольная, 1 — прямоугольная, 2-случайный наброс), следующий кодирует метод объединения в подпопуляции (0 — по минимальному расстоянию, 1 — лучший с худшими). Схематично хромосома показана на рисунке 3.

Рисунок 3 Схематичное представление хромосомы

3.2 Наброс

Первоначальный наброс осуществляется случайным образом. Генерируется 10 хромосом, описывающих структуру алгоритма.

3.3 Вычисление функции приспособленности

Функция приспособленности рассчитывается для каждой хромосомы по алгоритму, структура которого в ней закодирована. Для вычисления функции приспособленности определено следующее генетическое представление. Хромосома представляется 20 генами, первые 10 из которых кодируют Х, вторые 10 кодируют У. Максимальное значение, которое могут принимать Х и У — 20, т. е. минимальное количество бит, необходимых для кодирования этого числа — 5. Т.к. шаг изменения Х-0,1 и У — 0.5, значит, после запятой максимально возможное число — 9, для его представления в двоичном виде необходимо 4 бита. Так как Х и У могут принимать как отрицательные так и положительные значения, необходимо отвести один бит для определения знака (1 — отрицательное, 0 — положительное). Итого получается, что для хранения значения Х и У необходимо 10 бит на каждый. Схематично хромосома показана на рисунке 4.

Рисунок 4 Схематичное представление хромосомы

Формирование первого поколения осуществляется путем наброса по узлам сетки и отбором заданного количества лучших точек.(рисунок 5) На рисунке 6 представлена таблица, куда выводится информация о особях популяции.

Рисунок 5 Наброс методом треугольной сетки

Рисунок 6 Первоначальное поколение в таблице вывода

В курсовом проекте рассматриваются 3 варианта сетки. Первый вариант — треугольная сетка. В зависимости от размера первой популяции строится треугольная сетка (рисунок 7, рисунок 8). Для размера популяции 8 особей строится сетка с 8 узлами, а для популяции 9−12 особей — с 12 узлами. Для каждого узла рассчитывается значение функции адаптации и затем отбирается заданное количество лучших точек.

Рисунок 7 Треугольная сетка для размера популяции 8 особей

Рисунок 8 Треугольная сетка для размера популяции 9−12 особей

Второй вариант — прямоугольная сетка. В зависимости от размера первой популяции строится прямоугольная сетка (рисунок 9, рисунок 10). Для размера популяции 8−9 особей строится сетка с 9 узлами, а для популяции 10−12 особей — с 13 узлами. Для каждого узла рассчитывается значение функции адаптации и затем отбирается заданное количество лучших точек.

Рисунок 9 Прямоугольная сетка для размера популяции 8−9 особей

Рисунок 10 Прямоугольная сетка для размера популяции 10−12 особей

Третий вариант — случайный наброс точек, при котором в случайных позициях сетки генерируется заданное количество точек первого поколения.

Рисунок 11 Случайный наброс начальной популяции

Далее выполняется разбиение популяции на подпопуляции. В курсовом проекте реализовано два метода: по наименьшему Евклидову расстоянию и по значению функции приспособленности (лучшая с худшей).

В первом методе (по наименьшему Евклидову расстоянию) рассчитывается расстояние по Евклиду от каждой точки начальной популяции до каждой другой. Точки с наименьшим расстоянием объединяются и из массива расстояний удаляются их значения расстояний с другими точками, а заносится новое (от середины отрезка, соединяющего точки до каждой другой точки). Так происходит до тех пор, пока точки не будут объединены на 3 подгруппы.

Во втором методе (по значению функции приспособленности (лучшая с худшей) все точки начальной популяции ранжируются по значению функции приспособленности. Далее, чтобы средние значения функций приспособленности точек в каждой подгруппе было примерно равным, проранжированный список точек делится на три части и поочерёдно в каждую подпопуляцию отправляется верхняя точка каждой части.

Далее внутри каждой подпопуляции выполняются одинаковые действия, описанные ниже.

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

Далее выполняется селекция родителей (формирование пар). Т.к. в каждой подпопуляции в результате отбора оказывается только 3 точки, в пару объединяются 2 наилучшие по значению функции приспособленности.

На следующем шаге происходит их скрещивание (одноточечное). Хромосомы рассекаются в случайной точке и обмениваются «хвостами».

Далее хромосомы мутируют (мутирует 1 ген). Генерируется случайное число в пределах [0,1] и, если это число меньше 0,3, то ген мутирует.

В случае, если номер поколения кратен 5, то подпопуляции обмениваются одной хромосомой.

И так далее пока не будет достигнуто заданное N поколение. Затем выбирается лучшее решение.

Это решение и будет являться значением функции приспособленности для заданной структуры алгоритма .

3.4 Группировка в подпопуляции

В данном курсовом проекте группировка начальной популяции в подпопуляции осуществляется по значению функции приспособленности (лучшая с худшей). Значение функции приспособленности определяется по вызову нижнего уровня РПГА со структурой, закодированной в хромосоме. Далее все последующие действия производятся внутри подпопуляций.

3.5 Отбор

Из первого поколения во второе переходят все хромосомы, а в последующие только небольшое количество наилучших по функции приспособленности хромосом. Это необходимо для того, чтобы популяции не разрастались.

3.6 Селекция

Осуществляется формирование пар родительских хромосом. Также по значению функции приспособленности — лучшая с лучшей.

3.7 Скрещивание

Генерируется случайное число от 0 до 19(соответствует размеру хромосомы). В этой случайной точке хромосомы, сформировавшиеся в пары, разрезаются и обмениваются своими частями.

3.8 Мутация

Для мутации генерируется случайное число от 0 до 1. Если это значение <0.3, то происходит мутация. Т. е. значение случайного бита хромосомы меняется на противоположное.

3.9 Условие окончания счёта

РПГА считается отработавшим, если количество поколений достигло 100. А наилучшая структура — та, которая являлась лучшей в своих подпопуляциях (достигала оптимума функции) наибольшее количество раз.

4. Программная реализация

В ходе выполнения курсового проекта использовался язык программирования C#. В роли среды разработки (IDE) использовалась Visual Studio 2010. Использовались только стандартные библиотеки.

4.1 Схема программного обеспечения

Рисунок 12 Схема приложения

На рисунке 13 приведена диаграмма классов согласно спецификации UML2.

Рисунок 13 Диаграмма классов

4.2 Описание основных методов

private void Main_value_function (List chList, double[] v)

Принимает в качестве параметров экземпляр набор хромосом, для каждой хромосомы из этого набора вычисляется значение функции адаптации ранжируется по её значению.

private void Main_Selection (List chList, int count, Color clr)

осуществляет отбор, селекцию, скрещивание и мутацию для набора хромосом, переданных ему в качестве входного параметра.

private void MainGroup ()

осуществляет группировку начальной популяции хромосом в подпопуляции.

private void ToBinary (List pointList, int count)

private void ToDecard (String chrom, List pList)

Осуществляют перекодировку набора хромосом из бинарного представления в десятиричное и обратно.

private void RandomNet ()

private void FillTriangleNet ()

private void FillRectangleNet ()

Осуществляют наброс начальной популяции хромосом.

4.3 Тестирование и руководство пользователя

После запуска приложения открывается окно, показанное на рисунке 14.

Рисунок 14 окно программы

Чтобы запустить структурную оптимизацию алгоритма необходимо нажать на кнопку «Запуск надстройки» и выбрать поиск минимального экстремума функции, установив флажок напротив «Минимизировать», или программа автоматически будет осуществлять поиск на максимум. Далее нужно дождаться отработки РПГА. В результате программа выдаст график, на котором будут отображаться экстремумы функции, внизу экрана выведется строка со значением функции в точке экстремума и координатами этой точки. В главной таблице отобразится структура каждого поколения: номер поколения, хромосомы, принадлежность каждой хромосомы к подпопуляции (отражается цветом), координаты наилучшей точки по результату отработки нижнего уровня РПГА с заданной структурой, закодированной в хромосоме, и значение функции в этой точке.

Рисунок 15 Результат оптимизации (на максимум)

Рисунок 16 Результат оптимизации (на минимум)

Заключение

В данном курсовом проекте была поставлена задача оптимизировать структуру распределённого параллельно генетического алгоритма при помощи распределённого параллельно генетического, используя начальное количество точек=10, количество поколений=100, наброс точек случайным методом, группировку в подпопуляции по значению функции приспособленности. В результате работы программы было определено, что оптимальной структурой распределённого параллельного генетического алгоритма для решения заданной функции на максимум является: наброс по прямоугольной сетке, начальное количество точек — 10, число поколений-10, метод группировки — по расстоянию. Максимальное значение исследуемой функции равно 1.116 325. Результат, полученный при помощи надстройки, разрабатываемой в курсовом проекте, можно сравнить с результатами, полученными при решении этой же задачи методом перебора. В результате перебора оптимальной структурой оказалась: кол-во точек — 10, кол-во поколений 100, метод наброса — треугольная сетка, метод группировки — по расстоянию. Идентичное значение функции было найдено за 10 поколений. Как видно, метод перебора не эффективен из-за большого количества вариантов структур, при помощи программного обеспечения, разработанного в курсовом проекте, было найдено более оптимальное решение.

Конспект лекций по дисциплине «Оптимизация проектных решений», Ковалёва И. Л., 2012 г.

Приложение

Листинг программы

private void Main_value_function (List chList, double[] v)

{

for (int b=0;b

{

string bit1 = chList[b]. Substring (1, 1);

string bit0 = chList[b]. Substring (0, 1);

string bit2 = chList[b]. Substring (2, 1);

string bit3 = chList[b]. Substring (3, 1);

end = false;

rows_number = 0;

_graphics = pictureBox1. CreateGraphics ();

_points.Clear ();

if (bit2 == «0»)

{

FillTriangleNet ();

}

else

{

if (bit2 == «2»)

{

RandomNet ();

}

else

{

FillRectangleNet ();

}

}

if (bit0 == «0») points_number = 8; else { if (bit0 == «1») points_number = 9; else { if (bit0 == «2») points_number = 10; else { if (bit0 == «3») points_number = 11; else points_number = 12; } } }

if (bit1 == «0») generaton_number = 10; else { if (bit1 == «1») generaton_number = 25; else { if (bit0 == «2») generaton_number = 50; else { if (bit0 == «3») generaton_number = 75; else generaton_number = 100; } } }

Value_Function (_points, buff2List, points_number);

ToBinary (_points, points_number);

ToDecard (chromosome_List, buffList, points_number, Pens. White);

rows_number = rows_number + points_number;

if (bit3 == «0»)

Group1(_points, points_number);

else Group2(_points, points_number);

for (int j = 0; j < generaton_number — 1; j++)

{

Selection (first_group, _points, points_number, Color. Yellow);

NumberOfGeneration—;

Selection (second_group, _points, points_number, Color. Blue);

NumberOfGeneration—;

Selection (third_group, _points, points_number, Color. Green);

if (NumberOfGeneration % 5 == 0)

{

int point = (int)(first_group.Count / 2);

int buffX = first_group[point]. X;

int buffY = first_group[point]. Y;

first_group.Remove (first_group[point]);

point = (int)(second_group.Count / 2);

first_group.Add (second_group[point]);

second_group.Remove (second_group[point]);

point = (int)(third_group.Count / 2);

second_group.Add (third_group[point]);

third_group.Remove (third_group[point]);

third_group.Add (new Point (buffX, buffY));

}

dataGridView2.Rows.Add ();

dataGridView2[0, NumberOfStructure — 1]. Value = NumberOfStructure. ToString ();

dataGridView2[1, NumberOfStructure — 1]. Value = points_number;

dataGridView2[2, NumberOfStructure — 1]. Value = generaton_number;

if (bit2 == «0») dataGridView2[3, NumberOfStructure — 1]. Value = «Треугольной сеткой» ;

else { if (bit2 == «1»)dataGridView2[3, NumberOfStructure — 1]. Value = «Прямоугольной сеткой»; else dataGridView2[3, NumberOfStructure — 1]. Value = «Случайно»; }

if (bit3 == «0») dataGridView2[4, NumberOfStructure — 1]. Value = «По расстоянию» ;

else dataGridView2[4, NumberOfStructure — 1]. Value = «По зачению ф-ии» ;

end = true;

for (int l = 0; l < second_group.Count — 1; l++)

{ first_group.Add (second_group[l]); }

for (int k = 0; k < third_group.Count — 1; k++)

{ first_group.Add (third_group[k]); }

Value_Function (first_group, buff2List, first_group.Count);

if (NumberOfGeneration > 1)

v[b] = valet;

if (mainNumberOfGeneration == 100) { main_value[main_index] = v[b]; main_index++; }

if (valet < 0.25) _graphics.DrawRectangle (ypen, first_group[0]. X + 123, first_group[0]. Y + 123, 3, 3);

else

{

if (valet >= 0.25 && valet < 0.5) _graphics.DrawRectangle (gpen, first_group[0]. X + 123, first_group[0]. Y + 123, 3, 3);

else

{

if (valet >= 0.5 && valet < 0.75) _graphics.DrawRectangle (bpen, first_group[0]. X + 123, first_group[0]. Y + 123, 3, 3);

else { _graphics.DrawRectangle (rpen, first_group[0]. X + 123, first_group[0]. Y + 123, 3, 3); }

}

}

//_graphics.DrawRectangle (rpen, first_group[0]. X + 123, first_group[0]. Y + 123, 3, 3);

NumberOfStructure++;

rows_number = 0;

_pointPaintNet.Clear ();

_points.Clear ();

first_group.Clear ();

second_group.Clear ();

third_group.Clear ();

dataGridView1.Rows.Clear ();

NumberOfGeneration = 1;

chromosome_List.Clear ();

}

}

private void Main_Selection (List chList, int count, Color clr)

{

List new_chromosome_List=new List ();

Random rnd = new Random ();

int point = int. Parse (Math.Round ((rnd.NextDouble () * 2+1), 0).ToString ());

if (mainNumberOfGeneration== 1) { for (int r = 0; r < chList. Count; r++) new_chromosome_List.Add (chList[r]); }

else for (int r = 0; r < 3; r++) new_chromosome_List.Add (chList[r]);

mainNumberOfGeneration++;

int chcount = new_chromosome_List.Count;

main_rows_number = dg. RowCount;

bool m = false;

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[0]. Substring (0, point) + new_chromosome_List[1]. Substring (point) == new_chromosome_List[i]) m = true; }

if (!m) new_chromosome_List.Add (new_chromosome_List[0]. Substring (0, point) + new_chromosome_List[1]. Substring (point));

m = false;

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[1]. Substring (0, point) + new_chromosome_List[0]. Substring (point) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[1]. Substring (0, point) + new_chromosome_List[0]. Substring (point));

double mutation = rnd. NextDouble ();

main_rows_number = dg. RowCount — 1;

int p1 = int. Parse (Math.Round ((rnd.NextDouble () * 3), 0).ToString ());

if (mutation < 0.3)

{

string str = string. Empty;

if (p1 == 0)

{

m = false;

str = Math. Round ((rnd.NextDouble () * 4), 0).ToString ();

while (new_chromosome_List[0]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 4), 0).ToString ();

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1));

while (new_chromosome_List[1]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 4), 0).ToString ();

m = false;

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1));

}

else

{

if (p1 == 1)

{

m = false;

str = Math. Round ((rnd.NextDouble () * 4), 0).ToString ();

while (new_chromosome_List[0]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 4), 0).ToString ();

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1));

while (new_chromosome_List[1]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 4), 0).ToString ();

m = false;

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1));

}

else

{

if (p1 == 2)

{

m = false;

str = Math. Round ((rnd.NextDouble () * 2), 0).ToString ();

while (new_chromosome_List[0]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 2), 0).ToString ();

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1));

while (new_chromosome_List[1]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 2), 0).ToString ();

m = false;

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1));

}

else

{

m = false;

str = Math. Round ((rnd.NextDouble () * 1), 0).ToString ();

while (new_chromosome_List[0]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 1), 0).ToString ();

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[0]. Substring (0, p1) + str + new_chromosome_List[0]. Substring (p1 + 1));

while (new_chromosome_List[1]. Substring (p1, 1) == str) str = Math. Round ((rnd.NextDouble () * 1), 0).ToString ();

m = false;

for (int i = 0; i < new_chromosome_List.Count; i++) { if (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1) == new_chromosome_List[i]) m = true; }

if (!m)

new_chromosome_List.Add (new_chromosome_List[1]. Substring (0, p1) + str + new_chromosome_List[1]. Substring (p1 + 1));

for (int i = 0; i < new_chromosome_List.Count; i++)

{

dg.Rows.Add ();

dg[2, i + main_rows_number]. Value = new_chromosome_List[i];

dg[0, i + main_rows_number]. Value = mainNumberOfGeneration;

dg[1, i + main_rows_number]. Style. BackColor = clr;

}

double[] value = new double[new_chromosome_List.Count];

Main_value_function (new_chromosome_List, value);

string buff2 = string. Empty;

double buff1 = 0;

bool flag = false;

if (mainNumberOfGeneration ≠ 100) Main_chromosom_List.Clear ();

else { for (int k = 0; k < new_chromosome_List.Count; k++) Main_chromosom_List.Add (new_chromosome_List[k]); }

while (!flag)

{

flag = true;

for (int i = 0; i < new_chromosome_List.Count-1; i++)

{

if (Minimize.Checked)

{

if (value[i] > value[i + 1])

{

flag = false;

buff1 = value[i];

value[i] = value[i + 1];

value[i + 1] = buff1;

buff2 = new_chromosome_List[i];

new_chromosome_List[i] = new_chromosome_List[i + 1];

new_chromosome_List[i + 1] = buff2;

}

}

else

{

if (value[i + 1] > value[i])

{

flag = false;

buff1 = value[i];

value[i] = value[i + 1];

value[i + 1] = buff1;

buff2 = new_chromosome_List[i];

new_chromosome_List[i] = new_chromosome_List[i + 1];

new_chromosome_List[i + 1] = buff2;

chList.Clear ();

for (int i = 0; i < new_chromosome_List.Count; i++) chList. Add (new_chromosome_List[i]);