Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







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





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

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

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



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

С = (с1,…, сm)-внешние параметры, характеризующие внешнюю по отношению к объекту среду и оказывающие влияние на его функционирование;

X= (х1,…, хn)-внутренние параметры, характеризующие свойства отдельных элементов объекта.

В определении конкретных значений внутренних параметров, называемых управляемыми переменными, фактически стоит акт принятия решения.

Объединенную совокупность внешних и внутренних параметров будем называть множеством входных параметров.

Величины, характеризующие свойства объекта в целом как системы, будем называть входными параметрами, которые можно только измерять или вычислять, но непосредственно изменять нельзя. Обозначим их вектором j= (j1,…,j2).

       
   

Наименьшей неделимой единицей биологического вида, подверженной действию факторов эволюции, является особь аtк в (индекс к обозначает номер особи, а индекс t – некоторый момент времени эволюционного процесса). В качестве аналога особи а'к в экстремальной задаче однокритериального выбора (1.3) примем произвольное допустимое решение x Є D, которому присвоено имя акt . Действительно, вектор управляемых переменных (х1, …, хn) – это наименьшая неделимая единица, характеризующая в экстремальной задаче (1.3) внутренние параметры на каждом t–м шаге поиска оптимального решения, которые изменяют свои значения в процессе минимизации критерия оптимальности Q(х).

Для описания особей введем два типа вариабельных признаков, отражающих качественные и количественные различия между особями в степени их выраженности:

качественные признаки – признаки, которые позволяют однозначно разделять совокупность особей на четко различимые группы;

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

       
   

Качественные признаки особи акt определяются из символьной модели экстремальной задачи (1.3) как соответствующая точке х с именем акt бинарная строка Е (x) и составляющие ее бинарные комбинации еθ1), …, еθn ).

 
 

В качестве гена – единицы наследственного материала, ответственного за формирование альтернативных признаков особи, примем бинарную комбинацию еθi), которая определяет фиксированное значение целочисленного кода βi управляемой переменной хi в обычном двоичном коде. Одна особь акt будет характеризоваться n генами, каждый из которых отвечает за формирование целочисленного кода соответствующей управляемой переменной. Тогда структуру бинарной строки Е(х) можно интерпретировать хромосомой, содержащей n сцепленных между собой генов, которые расположены в линейной последовательности «слева – направо». Согласно хромосомной теории наследственности передача качественных признаков еθi ), i = 1, n, закодированных в генах, будет осуществляться через хромосомы от «родителей» к «потомкам».

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

Хромосому (2.9), содержащую в своих локусах конкретные значения аллелей, будем называть генотипом (генетическим кодом) Е(акt ), который содержит всю наследственную генетическую информацию особи акt , получаемую от « предков» и передаваемую затем «потомкам». Конечное множество всех допустимых генотипов образует генофонд. Для дихотомического разбиения мощность генофонда равна Cnnt .

Будем считать, что популяция Pt = (а1t,…, аvt) представляет собой репродукционную группу – совокупность из v особей, любые две из которых акt, а1t Є Pt, k ≠ 1 могут размножаться, выступая в роли «родителей» (акt – “мать”; а1t – “отец”). Здесь под размножением понимается свойство особей акt Є P воспроизводить одного или нескольких себе подобных непосредственных “потомков” (“детей”) b1t , i ≥ 1 и обеспечивать у них непрерывность и наследственную преемственность качественных признаков «родителей».

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

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

 

Контрольные вопросы и задания

1. Какие основные составляющие определяют понятие дискрет­ный автомат? Основные классы автоматов.

2. Какими функциями и какой математической теорией описы­ваются функционирование логического автомата?

3. Какие элементарные функции используются для описания логических автоматов? В чем суть табличного задания логических функций? Что такое дизъюнктивная форма?

4. Чем отличаются автоматы с конечной памятью? Математи­ческое описание переходов автомата с конечной памятью из одного состояния в другое. Как технически реализуется элемент задержки в автоматах с конечной памятью? Приведите пример.

5. Понятие алгоритма. Какими общими свойствами характеризуется любой алгоритм? Дайте пояснение этим эмпирическим свойствам на примере алгоритма Евклида определения наибольшего общего де­лителя. Какие используются математические формулировки понятия "алгоритм"?

6. Как вводится понятие алгоритма в некотором алфавите? Что такое ассоциативное исчисление? Эквивалентность алгоритмов. В чем суть определения нормального алгоритма Маркова? Поясните схему доказательства алгоритмической неразрешенности.

7. В чем необходимость сведения любого алгоритма к числен­ному? Что дает введение нумерации? Какую роль в сведении алго­ритма к численному играет метод нумерации Гёделя?

8. Как вводится математическая формулировка алгоритма через понятие автомата. В чем суть абстрактной схемы автомата с беско­нечной памятью в виде машины Тьюринга. Поясните функционирование машины Тьюринга на примере табл. 3.3 и 3.4.

9. Составить таблицу для логической функции, задаваемой следующим выражением: f(X1 , X2 , X3) = X1 , X2 , X3 v X1 , X2 , X3 v X1 , X2 , X3 .

10. Напишите для функции, заданной табл. 3.5. дизъюнктивную нормальную форму. Упростите ее.

Таблица 3.5

Х1 X2 Х3 f(X1 , X2 , X3)
       
       

 

11. Функция Х1®Х2 (импликация) (читается: "из Х1 следует Х2") задается табл. 3.6

 

Таблица 3.6

X1 X1 f(X1 , X2)

Напишите дизъюнктивную нормальную форму.

12. Напишите логическое выражение в переменных p, q, r для следующего высказывания: "Если вечером пойдет дождь, мы не пой­дем в кино и будем заниматься".

13. Путешественник попал к людоедам. Они разрешают ему про­изнести какое-либо высказывание и ставят условие, что если его высказывание будет истинным, то его сварят, а если ложным - то зажарят. Какое высказывание нужно произнести путешественнику. чтобы избежать гибели?

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.