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

В ходе исследования поставлены следующие задачи :

1. Сформировать общие представления о генетических алгоритмах

и их особенностях;

2. Выяснить, какие существуют генетические операторы;

3. Узнать, каким образом происходит работа генетического алгоритма

и его реализация;

4. Узнать, где могут применяться генетические алгоритмы;

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

алгоритмов;

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

алгоритмов;

7. На основе полученной информации создать электронное пособие по

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

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

Курсовая работа состоит из введения, трех глав основной части, заключения, приложения и библиографического списка.

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

В первой главе рассмотрены общетеоретические вопросы по теме «Генетические алгоритмы». В ней рассматривается, что такое геометрические алгоритмы, каковы их особенности, какие существуют генетические операторы, как работают геометрические алгоритмы.

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

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

ГЛАВА 1 ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ

1.1 Генетический алгоритм и его особенности

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

Идею генетических алгоритмов высказал Джон Холланд в 1975 году. Он заинтересовался свойствами процессов естественной эволюции, в том числе фактом, что эволюционируют хромосомы, а не сами живые существа. Холланд был уверен в возможности составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи так, как это делает природа - путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими последовательностями двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные процессы в поколениях таких хромосом. Так же, как и в природе, генетические алгоритмы осуществляли поиск "хороших" хромосом без использования какой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособленность. [7]

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

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

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

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

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

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

Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. В реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. [9]