Московский государственный технический университет 

им. Н.Э.Баумана

 

 

 

 

 

 

Утверждаю:	_____________________
	"___"_____________2006  г.

 

 

 

 

 

 

Отчёт по лабораторной работе №4

по дисциплине Интеллектуальные системы

" Решение задач с помощью генетических алгоритмов"

 

 

 

отчет

(вид документа)

 

 бумага А4

(вид носителя)

 

6

 (количество листов)

 

 

 

ИСПОЛНИТЕЛЬ:
	____________________
	"26"  апреля  2006 г.

 

 

 

 

 

 

 

 

 

 

 

1. Название и цель работы

Название: " Решение задач с помощью генетических алгоритмов ".

Цель: Ознакомиться с подходом к решению оптимизационных задач с помощью

      генетических алгоритмов (ГА).

 

2. Задания

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

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

 

3. Краткое описание предметной области и выбранной задачи

Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. Например, ГА могут использоваться, чтобы проектировать структуры моста, для поиска максимального отношения прочности/веса, или определять наименее расточительное размещение для нарезки форм из ткани. Они могут также использоваться для интерактивного управления процессом, например на химическом заводе, или балансировании загрузки на многопроцессорном компьютере.

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

где 1, 2,…,n – номера компьютеров , а веса дуг - a12, a13, a14,  ….. – длина пути между соответствующими вершинами.

           ГА  работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы.) Наиболее приспособленные особи получают возможность "воспроизводит" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.

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

 

4. Блок-схема с пояснениями выбранного ГА и каждого оператора в отдельности.

 

 

На рисунке представлена блок-схема выбранного ГА.

Рассмотрим каждый из его операторов:

1) Создание популяции

С помощью генерации случайных чисел создается начальная популяция из 20 особей.

 2) Селекция

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

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

3) Скрещивание

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

5) Редукция

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

5) Мутация

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

 

5. Протоколы проведенных экспериментов.

 

Создание популяции, первое поколение:

 

Следующее поколение:

Прохождение через 50 поколений и получение оптимального пути:

Как видно: за несколько шагов (<50)  мы прошли от особи с суммой=59 до особи с суммой =15, где сумма – это обратный показатель приспособленности – стоимость прохождения пути от 1 до 10 компьютера.

 

6. Выводы и рекомендации по использованию разработанных ГА.

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