2.4Вывод к Главе 2

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

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

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

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

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

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

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

ГЛАВА З РАЗРАБОТКА УЧЕБНОГО ЭЛЕКТРОННОГО ПОСОБИЯ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ

3.1 Обоснование выбора программного обеспечения

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

Интерактивность – сегодня очень важное условие для создаваемых приложений, программ, электронных пособий и т. д. Наиболее полный стандарт, который гарантирует данное условие, ActionScript для Flash. Сравнительно недавно он превратился из простого языка подготовки сценариев в полноценную объектно-ориентированную среду программирования.

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

Поэтому для создания электронного пособия по основам генетических алгоритмов был выбран Flash.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Вентцель Е.С. «Исследование операций», - М.: 1972 г.

2. «Генетические алгоритмы: почему они работают?»/, «Компьютерра», № 11, 1999

3. «Генетические алгоритмы и машинное обучение»

http://www.math.tsu.ru/russian/center/ai_group/ai_collection/docs/faqs/ai/part5/faq3.html

4. Исаев С. Популярно о генетических алгоритмах

www.algolist.manual.ru

5. «Нейропроект. Аналитические технологии XXI века» http://www.neuroproject.ru/genealg.php#what

6. Коршунов Ю.М. «Математические основы кибернетики. Для студентов вузов», - М.: 1987 г., стр. 67-89