Решение задач на тему: Генетические алгоритмы. Естественный отбор в природе. Представление объектов. Кодирование признаков

Введение

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

На мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в Природе. Поэтому не удивительно, что ученые, занимающиеся компьютерными исследованиями, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в естественных системах, была очень привлекательной. Эта надежда является причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.

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

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

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

Объектом изучения данной курсовой работы являются генетические алгоритмы.

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

Методы исследования:

- сбор и анализ литературных источников по данной теме;

- изучение особенностей создания и использования генетических алгоритмов;

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

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

Задачи:

1. проанализировать возможности генетических алгоритмов;

2. изучить особенности генетических алгоритмов;

3. создание электронного пособия по основам генетических алгоритмов;

Оглавление

- Введение

- Генетические алгоритмы 1.1 Естественный отбор в природе

- Представление объектов. Кодирование признаков

- Основные генетические операторы

- Схема функционирования генетического алгоритма Вывод

- Задачи оптимизации 2.1 Задачи, решаемые с помощью генетических алгоритмов

- Математическая постановка задачи оптимизации

- Решение Диофантова уравнения

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

- Задача коммивояжера Вывод

- Программная реализация. Создание пособия по генетическим алгоритмам 3.1 Обоснование выбора программного обеспечения

- Описание программной реализации Заключение

- Библиография

Список литературы

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

2. Гальцына О.Л., Попов И.И. "Основы алгоритмизации и программирования".

3. Грешилов А.А. "Как принять наилучшее решение в реальных условиях", - М.: 1991 г., стр. 164-170

4. Корнеев В.В., Гареев А.Ф. "Базы данных. Интеллектуальная обработка данных", М.: 2001г., стр. 220

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

6. Леонов О.И. "Теория графов".

7. Майника Э., "Алгоритмы оптимизации на сетях и графах." - М.: 1981

8. Новиков Ф.А. "Дискретная математика для программистов".

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

10. Де Джонг К. А. Введение ко второму специальному выпуску по

генетическим алгоритмам. Машинное обучение, №5(4), с. 351-353

11. Электронные источники:

12. "Генетические алгоритмы по-русски" - http://www.chat.ru/~saisa

13. "Нейропроект. Аналитические технологии XXI века" - http://www.neuroproject.ru

14. "Научное издательство ТВП" - http://www.tvp.ru/mathem3.htm

15. "Факультет вычислительной математики и кибернетики МГУ (ВМиК)" - http://cmc.сs.msu.su/labs/lvk/materials/tez_sapr99_1.html

17. "Журнал "Автоматизация Проектирования"" - http://www.opensystems.ru/ар/1999/01/08.htm

18. "(EHIPS) Генетические алгоритмы" - http://www.iki.rssi.ru/ehips/genetic.htm

19. "SENN Генетические Алгоритмы" - http://fdmhi.mega.ru/ru/senn_ga.htm

20. Хорева Е.В. Курсовая работа. Тема "Применение генетических алгоритмов для решения задач оптимизации"-КГПУ.: 2007г.

21. "Лекции по нейронным сетям и генетическим алгоритмам" - http://infoart.baku.аz/inews/30000007.htm