Приминение генетического алгоритма при решения задач безусловной оптимизации

Найдем глобальный минимум ,в том случае когда все переменные в интервале (-500.0; 500.0). И будем искать его прямым перебором m значений функции для m значений каждого аргумента на заданных интервалах [3]:

Этап 1: поиск минимумов на первоначально заданной грубой сетке итерациями. На каждой итерации сетка сдвигается случайно в пределах начальных значений шага ячейки;

Этапы 2,3,...: на каждом этапе область определения уменьшается и строится всё более мелкая сетка. Область определения охватывает лишь точки с минимумами. Каждый этап - это такие же итерации, что и на первом этапе.

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

Используя следующие  начальные параметры (Рисунок 7):

Рисунок 7 

Результаты  полученных расчетов можно увидеть  на рисунке 8, и соответствующий график минимумов представлен на рисунке 9.

Рисунок 8

Рисунок 9

 

2. РЕШЕНИЕ ЗАДАЧИ О РАНЦЕ

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

1929 год. В США великая  депрессия, введен сухой закон.  Страна просто задыхается без  спиртного. В этот сложный момент  группа инициативных граждан  под руководством Аль Капоне решает помочь родной стране. Ими планируется поставка алкогольной продукции из Ливерпуля в Штаты. Благодарные сограждане из 5 крупных городов США готовы платить большие деньги за тонну спиртного: 2000  - 250 долл. в Бостоне, 3000 -300  в Детройте, 2500 -500 в Вашингтоне, 3200 -100 в Нью-Йорке и 1800 -- 600 долл в Чикаго. Все 5 городов находятся на разном расстоянии от порта, куда прибывает груз: Бостон –миль, Детройт –миль, Вашингтон – 500 миль, Нью-Йорк –100 миль и Чикаго –миль. Требуется выбрать города, в которых можно получить максимальную прибыль от продажи спиртного. При этом суммарное расстояние от этих портов до порта с грузом не должно превышать 1000 миль.

2. Решение задачи.

Решим данную задачу о ранце  методом ветвей и границ.

Данная задача является задачей  о ранце вида:

,       (1)

где критерием является функция

,         (2)

которая может быть устремлена и к максимуму, и к минимуму.

Для начала составим следующую  математическую модель:

Пусть – j-тый город, откуда соответственно . При этом, если в j-тый город будет разгружаться алкогольная продукция, то , иначе . Другим ограничением будет являться суммарное расстояние до порта с грузом. Таким образом:

;

Целевой функцией или критерием  будет являться максимальная благодарность  сограждан:

.

Далее отбираем порты по приоритетности, т.е. в порядке убывания отношения  :

(3); (2); (4); (1); (5).

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

, ;

Аналогично рассуждая, далее  получаем:

, ;

, ;

В последнем случае оставшееся после других городов расстояние меньше 500 миль, поэтому  будет дробным: , => .

Таким образом, начальный  опорный план: .

Значение целевой функции: .

Но  обязательно целое. Поэтому чтобы определить, чему все же равен : 0 или 1 вычислим следующие значения:

;– целая часть критерия  при существующем опорном плане. 

;– значение критерия при  целочисленном опорном плане,  т.е.  .

Множество D, которому принадлежит имеет , . Разделим его на 2 подмножества, такие что:

;

- здесь  .

- здесь  .

1) Анализ множества  D₁.

Поскольку целевая функция и ограничения будут иметь вид:

Строим новый опорный  план:

, ;

, ;

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

2) Анализ множества  D₂.

Поскольку целевая функция и ограничения будут иметь вид:

=> .

Строим новый опорный  план:

, ;

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

3) Отсев неперспективного  подмножества.

.

Так как  и больше Rec, то оба подмножества можно считать перспективными, но поскольку , то далее мы будем исследовать подмножество D₂. Разделим его на 2 подмножества, такие что:

;

- здесь  .

- здесь  .

4) Анализ множества  D₃.

Поскольку , целевая функция и ограничения будут иметь вид:

.

Строим новый опорный  план:

, ;

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

5) Анализ множества  D₄.

Поскольку , целевая функция и ограничения будут иметь вид:

=> .

Строим новый опорный  план:

, ;

Т.к. , поэтому будет дробным: , => .

Таким образом, новый опорный  план: .

;

, при  .

6) Отсев неперспективного  подмножества.

.

Так как  и больше Rec, то оба подмножества можно считать перспективными, но поскольку , то далее мы будем исследовать подмножество D₃. Разделим его на 2 подмножества, такие что:

;

- здесь  .

- здесь  .

7) Анализ множества  D₅.

Поскольку , , целевая функция и ограничения будут иметь вид:

.

Строим новый опорный  план, очевидно: . При , ограничение выполняется всегда.

;

, при  .

8) Анализ множества  D₆.

Поскольку , , целевая функция и ограничения будут иметь вид:

.

Ограничение несовместное, поскольку даже при оно не выполняется. Следовательно множество D₆ не существует.

Таким образом, оптимальным  планом данной задачи будет: , то есть алкоголь выгоднее всего поставлять в 3 города: Детройт, Вашингтон и Нью-Йорк. При этом прибыль составит 8700 долл.

 

ГЛАВА 4 РЕЗУЛЬТАТЫ ЧИСЛЕННОГО ЭКСПЕРИМЕНТА

4.1 МИНИМИЗАЦИЯ ФУНКЦИИ ШВЕФЕЛЯ

Нахождения минимума функции  Швефеля  с применением генетического  алгоритма будем выполнять при  следующих начальных условиях:

// Количество хромосом (неизвестных  в функции Швефеля)

int chromosomesCount = 15;

// Максимальное количество  поколений (итераций)

int maxGeneration = 10000;

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

int maxEqualGeneration = 300;

// Если на очередной  итерации целевая функция изменилась  на значение,

меньшее ил равное minDelta, то считаем, что целевая функция не изменилась.

double minDelta = 1e-8;

// Максимальный размер  популяции

int populationMaxSize = 100;

// Вероятность мутации

double mutationPossibility = 0.1;

// Вероятность скрещивания

double crossPossibility = 0.9;

// Интервал изменений  хромосом

double chromoMinVal = -500;

double chromoMaxVal = 500;

При этом получим следующий  результат (Рисунок 10):

 

Рисунок 10

4.2 РЕШЕНИЕ ЗАДАЧИ О РАНЦЕ

На следующем рисунке (Рисунок 11) приведено решение данной задачи с применением генетического  алгоритма:

Рисунок 11

В данной программе были использованы следующие  начальные  данные :

// число особей в популяции

           public static int populationCount = 200;

 // максимальный вес, который может содержатьcя в рюкзаке

           public static double maxWeightKnapsack = 1000;

// массив из элементов,  положить в рюкзак

          public static Item[] items = new Item[]{

  new Item(250,2000),

  new Item(300,3000),

  new Item(500,2500),

  new Item(100,3200),

            new Item(600,1800) };   

// вероятность (в процентах)  мутации

           public static double mutationLikelihood = 0.9;

// Число лиц, участвующих  в турнире выбора

         public static int tournamentParticipantsCount = 5;    

// Число "поколений".

         public static int maxIterations = 200;

 

ЗАКЛЮЧЕНИЕ

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

Можно выделить следующие  преимущества генетических алгоритмов:

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

2) ГА хорошо применимы  к задачам оптимизации в крупных  масштабах.

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

4) Они достаточно просты в реализации, но при этом могут быть использованы для широкого класса задач.

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

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

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

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

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Холланд Дж. , Генетические алгоритмы / Холланд Дж. // В мире науки. –1992. –  № 9-10.
2. Генетический алгоритм [Электронный ресурс]/Википедия .– Моска, 2010.  – Режим доступа:

 http://ru.wikipedia.org/wiki/ Генетический_алгоритм #cite_note-book-0.  – Дата доступа: 30.10.2012

3. Определения глобального минимума целевой функции [Электронный ресурс]/  У чебный сайт КГМТУ – Режим доступа: http://pvn.ho.ua/pvn.org.ua/www/lection/example/example_6/6_8/NonLinerOpt_auto/greedy_2arg_auto.html. – Дата доступа: 28.11.2012
4. Рутковская Д., Нейронные сети, генетические алгоритмы как нечёткие системы/ Рутковская Д., Пилиньский М., Рутковский Я.. – Москва.: Горячая линия – Телеком, 2004  – с..