АННОТАЦИЯ 

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

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

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

     The Genetic algorithms are broadly used for intellectual data processing and decisions of the problems optimization and of searching for at present times. They are successfully used for decision of the economic significant problems in business and engineering development. The Financial companies broadly use the genetic algorithms for forecasting of the development the financial.

     The problems of optimization are one of the most important classes of the problems of the practical character. We have deal with these problems every day at work and at home.

     What are the genetic algorithms and how can we use the genetic algorithms for decision of the problems of optimization is offered realize in this scientific work.

 

      СОДЕРЖАНИЕ 

ВВЕДЕНИЕ

 

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

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

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

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

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

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

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

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

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

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

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

2. Выяснить, какие существуют генетические операторы;
3. Узнать, каким образом происходит работа генетического алгоритма

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

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

алгоритмов;

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

алгоритмов;

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

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

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

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

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

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

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

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

 

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

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

 

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

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

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

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

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

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

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

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

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

     Генетические алгоритмы работают с совокупностью "особей" – популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах.[13]

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

     Генетический  алгоритм состоит из следующих компонент:

• Хромосома. Решение рассматриваемой проблемы. Состоит из генов.
• Начальная популяция хромосом.
• Набор операторов для генерации новых решений из предыдущей