Реферат на тему Генетические алгоритмы

Содержание:

СОДЕРЖАНИЕ 5

ВВЕДЕНИЕ 6

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

1.1 АЛГОРИТМ: ПОНЯТИЯ И СВОЙСТВА 7

2. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ. ОСНОВНЫЕ ПОНЯТИЯ 9

2.1 ПОНЯТИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 9

2.2 ОПЕРАТОРЫ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 11

2.3 ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 12

ЗАКЛЮЧЕНИЕ 18

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

Введение:

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

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

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

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

Заключение:

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

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

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

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

— изучено понятие генетический алгоритм;

— изучены возможности генетических алгоритмов;

— изучены операторы генетических алгоритмов.

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

Преимущества генетических алгоритмов:

·- не требуют никакой информации о поведении функции (например, дифферен-цируемости и непрерывности);

·- относительно стойки к попаданию в локальные оптимумы;

·- пригодны для решения крупномасштабных задач оптимизации за счет эффек-тивного распараллеливания;

·- могут быть использованы для широкого класса задач;

·- просты в реализации;

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

Программа разработана в соответствии с заданием.

Фрагмент текста работы:

1 Генетические алгоритмы

1.1 Алгоритм: понятия и свойства

Алгоритм (от латинской формы имени среднеазиатского математика аль-хорезми) — правило действий, последовательность проведения вычислительных операций, способ нахождения искомого результата. В традиционной трактовке алгоритм — это точ-ный набор инструкций, описывающих последовательность действий исполнителя для до-стижения результата решения задачи за конечное время. По мере развития параллельно-сти в работе компьютеров слово «последовательность» стали заменять более общим сло-вом «порядок» [3].

Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми. Ранее часто писали «ал-горифм», сейчас такое написание используется редко. Часто в качестве исполнителя вы-ступает некоторый механизм (компьютер, токарный станок, швейная машина), но поня-тие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом — в таком слу-чае исполнителем является человек. Понятие алгоритма — одно из основных в программи-ровании и информатике.

Это последовательность команд, предназначенная исполнителю, в результате выполнения которой он должен решить поставленную задачу. Алгоритм должен описы-ваться на формальном языке, исключающем неоднозначность толкования. Исполнитель может быть человеком или машиной. Исполнитель должен уметь выполнять все команды, составляющие алгоритм. Множество возможных команд конечно и изначально строго за-дано. Действия, выполняемые по этим командам, называются элементарными. Запись ал-горитма на формальном языке называется программой. Иногда само понятие алгоритма отождествляется с его записью, так что слова «алгоритм» и «программа» — почти синони-мы. Небольшое различие заключается в том, что под алгоритмом, как правило, понимают основную идею его построения.

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

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

Б. Понятность — алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т.е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. Алгоритм всегда рассчитан на выполнение «не размышляющего» исполнителя. Алгоритм составляется из команд, входящих в СКИ.

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

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

Д. Массовость — алгоритм пригоден для решения любой задачи из некоторого класса задач, т.е. алгоритм правильно работает на некотором множестве исходных дан-ных, которое называется областью применимости алгоритма. Свойство массовости опре-деляет скорее качество алгоритма, а не относится к обязательным свойствам (как дис-кретность, понятность и пр.).

Существуют алгоритмы, область применимости которых ограничивается един-ственным набором входных данных или даже отсутствием таковых (например, получение фиксированного числа верных цифр числа p).

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