Описание программной реализации

 

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

Затем были определены структура и дизайн пособия.

Электронное учебное пособие создавалась с помощью Macromedia Flash MX2004.

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

На первой странице было размещено название пособия и его содержание. Содержание состоит из трех пунктов, которые в свою очередь делятся на подпункты, позволяющие осветить рассматриваемую тему с нескольких сторон (Рисунок 2):

Рисунок 2 Содержание электронного пособия

Перелистывание между слайдам осуществляется за счет навигации в виде двух стрелок «вперед»-«назад», расположенных в правом нижнем углу. Кроме того, всегда существует возможность вернуться к странице содержания с любой страницы пособия. Для этого достаточно воспользоваться кнопкой «Main». Для того, чтобы кнопки навигации работали, на них был написан сценарий на Action Script.

Подпункты на странице содержания выполнены в виде ссылок. Достаточно нажать на интересующий вопрос и откроется его страничка.

Каждый пункт и подпункт презентации расположен на отдельной странице. Для презентации был выбран нейтральный голубой фон. Вся цветовая гамма выдержана. Шрифты были подобраны таким образом, чтобы можно было прочитать без затруднений. В презентации присутствуют рисунки и таблицы, более наглядно объясняющие те или иные аспекты вопроса (Рисунок 3):

Рисунок 3 Пример страницы с наглядными пояснениями

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

В электронном пособии в качестве примера оптимизационной задачи, которую можно решить с помощью генетического алгоритма, представлена задача коммивояжера. Для иллюстрации реализации генетического алгоритма при решении задачи была создана программа в Borland Delphi 6.0, которая, в частности показывает решение задачи, представленной в электронном пособии (Рисунок 4):

 

Рисунок 4 Реализация задачи коммивояжера с помощью генетического алгоритма

 

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

ЗАКЛЮЧЕНИЕ

 

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

Также было выяснено, какие задачи можно решать с помощью генетических алгоритмов. Среди таких задач находятся и особый класс – оптимизационные.

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

Итак, наша гипотеза о том, что задачи оптимизации можно решить с помощью генетических алгоритмов нашла свое подтверждение.

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

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

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

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