Нельзя  отождествлять критерий (критерии) оптимальности и целевую функцию.

     Целевая функция – это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.

     Отличие понятий «критерий» и «целевая функция» состоит в следующем:

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

 экстремума:

     Различают два вида задач оптимизации:

1. Задачу минимизации.
2. Задачу максимизации.

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

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

     В общем виде находится именно вектор, т.к., например, при решении двухпараметрической  задачи, он будет включать в себя два параметра, трехпараметрической – три параметра и т.д. [1]

     2.3 Пути решения оптимизационных задач

 

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

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

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

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

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

     Типичная  практическая задача, как правило, мультимодальна  и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение. [1]

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

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

 

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

 

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

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

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

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

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

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

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

 

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

     

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

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

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

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

     

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

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

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

     

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

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

 

ЗАКЛЮЧЕНИЕ

 

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

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

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

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

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

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

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