Курсовая работа на тему «Виртуализация генетического алгоритма». Методические указания

7 Визуализация генетического алгоритма

Генетический алгоритм – алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, аналогичных естественному отбору в природе. Генетические алгоритмы не являются гарантированно точными или оптимальными, но достаточны для решения поставленной задачи (Генетические алгоритмы : учеб. пособие / Л. А. Гладков, В. В. Курейчик, В. М. Курейчик. – 2-е изд. – М. : Физматлит, 2006. – 320 с.).

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

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

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

Таким критерием может быть:

• нахождение глобального решения,

• исчерпание числа поколений, отпущенных на эволюцию,

• исчерпание времени, отпущенного на эволюцию,

• исчерпание времени на улучшение предыдущего результата.

Генетические алгоритмы служат главным образом для поиска решений в многомерных пространствах поиска.

В рамках курсового проекта должны быть реализованы:

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

2. С момента запуска основного цикла начинается демонстрация движения особей. Когда текущее поколение прекращает существование, стартует следующая «итерация» основного цикла, особи нового поколения начинают движение из начальной точки. И так далее для последующих поколений. Другими словами, пользователь сможет наблюдать движение особей каждого поколения.

3. В случае если сходимость алгоритма происходит слишком медленно, пользователь имеет возможность пропустить показ некоторого количество поколений.

4. Меню «О программе», содержащее вкладки «Справка», «О разработчике».