Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «ВГУ»)

Факультет Прикладной математики, информатики и механики

Кафедра математических методов исследования операций

РЕШЕНИЕ ЗАДАЧИ ПОВЫШЕНИЯ НАДЕЖНОСТИ РЕЗЕРВИРОВАНИЯ С ПОМОЩЬЮ ЭВОЛЮЦИОННОГО МОДЕЛИРОВАНИЯ

Выпускная квалификационная работа бакалавра

Направление 010500 «Прикладная математика и информатика»

Допущен к защите в ГАК «___»_____ 201_ года

Зав. кафедрой Баскаков А.Г.

Д.ф.-м.н., профессор

Исполнитель Гальцев Я.С.

Руководитель Каширина И.Л.

К.т.н., доцент

Воронеж 2012



Оглавление

Введение.

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

1.1 Общие сведения о надежности аппаратных средств и методах резервирования

1.2 Архитектура систем управления огневыми испытаниями ЖРД

Глава 2. Основы теории надежности

2.1 Теория надежности как наука, понятие надежности и отказа

2.2. Терминология теории надежности

2.3 Критерии надежности невосстанавливаемых систем

2.4 Экспоненциальное распределение времени до отказа.

Глава 3. Математическая модель выбора вариантов резервирования компонентов стендовой информационно-управляющей системы

Глава 4. Генетические алгоритмы.

4.1 Общая схема генетического алгоритма

4.2 Создание начальной популяции

4.3 Отбор (селекция)

4.4 Скрещивание (кроссовер)

4.5 Мутация

4.6 Формирование новой популяции.

Глава 5. Генетический алгоритм решения задачи выбора вариантов резервирования компонентов стендовой информационно-управляющей системы

Глава 6. Разработка приложения

6.1 Требования к приложению.

6.2 Особенности реализации.

6.3 Графический интерфейс

6.4 Тестирование приложения, определение оптимальных параметров

Заключение

Список использованных источников

Приложение А. Листинг программы

Введение

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

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

Для достижения поставленной цели были выполнены следующие этапы:

1. Изучение сути проблемы данной задачи;

2. Изучение основы теории надежности;

3. Изучение математической модели данной задачи;

4. Разработка алгоритмов решения задачи;

5. Программная реализация;

6. Тестирование программы.



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

1.1 Общие сведения о надежности аппаратных средств и методах резервирования

При проведении огневых испытаний жидкостных ракетных двигателей (ЖРД) предъявляются особые требования к безотказности технических средств автоматизированных систем управления технологическими процессами (АСУТП). Одними из основных показателей безотказности технических средств АСУТП являются среднее время наработки на отказ и вероятность безотказной работы.

Одним из самых радикальных способов повышения безотказности (надежности) является резервирование. В промышленной автоматизации наибольшее распространение получили следующие методы резервирования: резервирование замещением «один из двух» (1оо2 - 1 out of 2) и метод мажоритарного голосования «два из трех» (2оо3). Системы без резервирования классифицируются как 1оо1.

1.2 Архитектура систем управления огневыми испытаниями ЖРД

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

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

На рис.1 представлена структурная схема резервирования 1оо2 для ключевых элементов. Условные обозначения: КУ- команда дискретного управления; ИП - источник питания; К1- ключ; ОУ- объект управления.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.1. Резервирование ключевых элементов по схеме 1оо2

надежность резервирование информационный управляющий

На рис.1 а ключи объединены по схеме ИЛИ. Недостатком данной схемы является то, что при возникновении отказа типа КЗ невозможно снять команду с объекта управления. Схема представленная на рис.1 б нечувствительна к отказам типа КЗ из-за наличия блока переключения на резерв. Однако данной схеме также присущи недостатки: блок переключения на резерв должен быть абсолютно надежным (а он в общем случае также состоит из ключей), требуется достаточно информативный сигнал диагностики для определения момента возникновения отказа, имеется ограничение по времени переключения на резерв. Для некоторых резервируемых элементов, такой блок переключения на резерв может просто отсутствовать.

На рис.2 а представлена классическая структурная схема резервирования 2оо3 для ключевых элементов.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Рис.2. Резервирование ключевых элементов по схеме 2оо3

Как видно из рис.2 а при классическом резервировании 2оо3 требуется в 6 раз больше ключей, чем в схеме 1оо1. Этот недостаток можно частично устранить, применив упрощенную схему рис.2 б. В схеме на рис.2 б всего 4 ключа и один вентиль (В). Назначение вентиля (В) заключается в том, чтобы разрешать подачу команды на ОУ только по направлению, указанному стрелкой. Вентиль обеспечивает совместную работу ключей К₁ и К₃. В качестве вентилей широкое применение нашли полупроводниковые диоды, надежность которых как минимум на порядок выше надежности ключей, поэтому анализе надежности всего ключевого элемента их можно вообще не учитывать. Тем не менее, эта схема остается самой дорогостоящей (по сравнению с 1оо1 и 1оо2).



Глава 2. Основы теории надежности

2.1 Теория надежности как наука, понятие надежности и отказа

Теория надежности -- наука, изучающая закономерности отказов технических систем. Основными объектами ее изучения являются:

· критерии надежности технических систем различного назначения;

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

· методы синтеза технических систем;

· пути обеспечения и повышения надежности техники;

· научные методы эксплуатации техники, обеспечивающие ее высокую надежность.

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

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

Отказом называется событие, после возникновения которого характеристики технического объекта (параметры) выходят за допустимые пределы. Это понятие субъективно, т. к. допуск на параметры объекта устанавливает пользователь. Отказ -- фундаментальное понятие теории надежности. Критерий отказа -- отличительный признак или совокупность признаков, согласно которым устанавливается факт возникновения отказа.

2.2 Терминология теории надежности

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

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

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

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

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

Наработка до отказа -- наработка объекта от начала его эксплуатации до возникновения первого отказа.

Средний срок службы -- математическое ожидание срока службы;

2.3 Критерии надежности невосстанавливаемых систем

Отказ элемента является событием случайным, а время о до его возникновения -- случайной величиной. Основной характеристикой надежности элемента является функция распределения продолжительности его безотказной работы F (t) = Р (о< t) , определенная при t > 0. На ее основе могут быть получены следующие показатели надежности невосстанавливаемого элемента:

· P(t) -- вероятность его безотказной работы в течение времени t;

· Q(t) -- вероятность отказа в течение времени t;

· f(t) -- плотность распределения времени безотказной работы;

· л(t) -- интенсивность отказа в момент времени t;

· T -- среднее время безотказной работы (средняя наработка до отказа);

Вероятностью безотказной работы называется вероятность того, что технический объект не откажет в течение времени t или что время о работы до отказа технического объекта больше времени его функционирования t:

Вероятность безотказной работы является убывающей функцией во времени, имеющей следующие свойства:



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

Плотность распределения времени безотказной работы -- это плотность распределения случайной величины . Она наиболее полно характеризует надежности техники в данный момент (точечная характеристика). По ней можно определить любой показатель надежности невосстанавливаемой системы. В этом основное достоинство плотности распределения времени безотказной работы.

Интенсивностью отказов называется отношение плотности распределения к вероятности безотказной работы объекта:

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

Средним временем безотказной работы называется математическое ожидание времени безотказной работы технического объекта:

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

Среднее время безотказной работы является интегральным показателем надежности. Его основное достоинство -- высокая наглядность.

2.4 Экспоненциальное распределение времени до отказа

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

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

Функция надежности

определяет вероятность безотказной работы за время

В данном случае интенсивность отказов есть величина постоянная:



Глава 3. Математическая модель выбора вариантов резервирования компонентов стендовой информационно-управляющей системы

Из главы 1 известно, что одними из основных показателей безотказности технических средств АСУТП являются среднее время наработки на отказ T и вероятность безотказной работы P(t).

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

;

где =const - интенсивность отказов.

При этом частота отказов по определению является плотностью распределения времени до отказа

Среднее время наработки на отказ T определяется следующим образом:

Также в главе 1 было сказано, что элементы установки могут быть резервированы тремя способами: 1oo1, 1oo2 и 2oo3.

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

а среднее время наработки на отказ

Рассмотрим резервированную систему, состоящую из двух элементов (1оо2). События A₁ и A₂ означают безотказную работу этих элементов, следовательно событие A, означающее безотказную работу всей системы определяется как

Учитывая, что элементы резервированной системы идентичны, вероятности событий A₁ и A₂ равны, эти события независимы, то вероятность безотказной работы системы 1оо2:

Тогда

Аналогично для резервированной схемы 2оо3 можно получить:



На рис.3 показаны вероятности безотказной работы систем 1оо1, 1оо2 и 2оо3 при =1год^-1.

Рис.3. Вероятность безотказной работы 1оо1, 1оо2 и 2оо3 при =1год^-1

Приравняв P_1oo1(t) к P_2oo3(t), можно узнать критическое время T_2oo3кр=TLn(2)0,7T, после которого вероятность безотказной работы системы 2оо3 становится меньше, чем у системы 1оо1, а использование резервирования становится неэффективным. Проанализировав P_1oo1(t) и P_1oo2(t), можно сказать, что вероятность безотказной работы системы 1оо2 всегда больше, чем у системы 1оо1, однако нельзя забывать про недостатки 1oo2, рассматриваемые в главе 1.

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

Каждому i-му компоненту может быть назначен один из трех вариантов резервирования: 1 - элемент ставится без резервирования (1оо1), 2 -резервирование замещением «один из двух» (1оо2), 3- метод мажоритарного голосования «два из трех» (2оо3). Пусть n- общее количество резервируемых компонентов.

Введем переменные:

1, если j-му компоненту назначается i-й вариант резервирования;

0, в противном случае; .

Важным ограничением является фиксированное среднее время безотказной работы системы (наработка до отказа).

Было показано, что среднее время безотказной работы элемента, резервируемого по схеме 1оо2, составляет 3/2 от среднего времени работы нерезервируемого элемента, а среднее время безотказной работы элемента по схеме 2оо3 соответственно равно 5/6 от среднего времени работы 1oo1.

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

Тогда первое ограничение имеет вид:

,

где T_j - cреднее время наработки на отказ j-го элемента системы без резервирования.

Поскольку каждому элементу назначается ровно один метод резервирования, вторая группа ограничений задачи имеет вид:

, ,

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

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

Поэтому первая целевая функция имеет вид:

Здесь - стоимость j-го элемента резервирования, G_j ?1- коэффициент, увеличивающий стоимость схемы 1оо2 в случае, если для данного резервируемого элемента существует надежный блок переключения на резерв; и G_j=S в случае, если такой блок отсутствует (S- максимально возможная суммарная стоимость резервируемых элементов, выполняет роль штрафного коэффициента). Заметим, что если стоимости резервируемых элементов примерно равны, то этот критерий можно интерпретировать как минимизацию общего количества элементов системы (а, следовательно, и ее габариты).

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

Пусть p_j - вероятность безотказной работы j-го элемента без резервирования. Тогда в схеме 1оо2 вероятность безотказной работы имеет вид , а в схеме 2оо3 эта вероятность равна . Таким образом, вторая целевая функция имеет вид:

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

, ,

.



Глава 4. Генетические алгоритмы

4.1 Общая схема генетического алгоритма

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

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

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

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

· нахождение глобального, либо субоптимального решения;

· исчерпание числа поколений, отпущенных на эволюцию;

· исчерпание времени, отпущенного на эволюцию.

Таким образом, можно выделить следующие этапы генетического алгоритма:

Ш Создание начальной популяции

начало цикла

Ш Отбор (селекция).

Ш Скрещивание (кроссовер).

Ш Мутация.

Ш Формирование новой популяции.

Ш Если условие останова не выполняется, то начало цикла, иначе

конец цикла

4.2 Создание начальной популяции

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

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

Обозначим начальную популяцию через , где -

i-ая особь (i=1,…,n), n - количество особей в популяции.

4.3 Отбор (селекция)

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

Оператор пропорциональной селекции также известен как «рулеточный» отбор. Принцип этого отбора состоит в следующем: особи располагаются на колесе рулетки так, что размер сектора каждой особи пропорционален ее приспособленности. Запуская рулетку, выбираем особей для дальнейшего скрещивания. Математически, это выглядит так: если событие A = «i-ая особь выбрана», f - функция приспособленности, P - вероятность наступления события, то P(A) = .

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

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

4.4 Скрещивание (кроссовер)

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

При одноточечном кроссовере случайным образом выбирается точка кроссовера - индекс вектора, которым представлена особь. Обозначим этот индекс через k. Пусть в скрещивании принимают участие две особи-родителя и . Тогда в результате скрещивания будут получены особи-потомки

,

.

Схематично это выглядит так:

1	1	0	1	1	0	1
0	0	1	0	1	1	0

1	1	0	1	1	1	0
0	0	1	0	1	0	1

При двухточечном кроссовере действует тот же принцип, что и при одноточечном кроссовере, только обмен частями векторов идет не от точки k до n, а от k₁ до k₂, где k₁, k₂ - точки двухточечного кроссовера:

,

.

Схематично это представляется так:

1	1	0	1	1	0	1
0	0	1	0	1	1	0

1	1	1	0	1	0	1
0	0	0	1	1	1	0

В равномерном кроссовере каждый бит первого потомка случайным образом наследуется от одного из родителей; второму потомку достается бит другого родителя.



4.5 Мутация

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

При одноточечной мутации каждый бит с определенной вероятностью подвержен изменению. Схематично это можно представить так:

1	0	1	0	0	1	0
v
1	0	1	0	1	1	0

При инверсии выбираются два индекса k₁ и k₂ (k₁ < k₂), затем биты с индексами k₁,…,k₂-1 располагаются в обратном порядке, т.е. если была особь , то после мутации она имеет вид . Схематично это выглядит так:

1	0	11	21	00	1	0
v v
1	0	00	-1	11	1	0

При транслокации происходит перенос части вектора в другой сегмент этого же вектора:

1	1	1	0	0	1	1
-
1	0	0	1	1	1	1

4.6 Формирование новой популяции

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



Глава 5. Генетический алгоритм решения задачи выбора вариантов резервирования компонентов стендовой информационно-управляющей системы

1-й этап. Представление данных.

Хромосома, представляющая неизвестную матрицу X, задается с помощью строкового кодирования. Суть кодирования заключается в следующем: экземпляр популяции - это строка длиною n (n- размерность задачи), в которой на i-м месте стоит j[1..3], если . Таким образом решение (фенотип) будет записано как “троичная” строка: x=(1,1,2,3,2,3,2) (генотип).

2-й этап. Генерация начальной популяции.

Первая популяция создаётся случайным образом из L различных “троичных” строк длиной n. Дополнительно (с целью улучшения генетического материала) в первую популяцию можно ввести строки, представляющие собой приближенные решения задач по обоим критериям в отдельности.

3-й этап. Оценка особей популяции по критерию приспособленности.

1) Для каждого решения в популяции вычисляется вектор целей , по которому далее определяется скалярное значение функции приспособленности.

2)Из текущей популяции выбирается множество недоминируемых внутри этой популяции решений, они запоминаются и временно выбрасываются из рассмотрения.

3)Далее ищется множество недоминируемых вариантов в усеченном множестве, и исключаются они. Эта процедура проделывается до тех пор, пока все варианты не будут исключены из популяции.

4)Теперь все строки ранжируются: принадлежащие последнему исключённому множеству получают ранг 1, предпоследнему ранг 2. Строки, первыми выброшенные из рассмотрения, получают самый высокий ранг. Внутри каждого исключенного множества все варианты решения имеют одинаковый ранг.

5)Далее, в отдельности для каждой группы строк одного ранга, происходит назначение оценок приспособленности. Предположим, ранг k имеет m строк. Тогда строка, сумма евклидовых расстояний от которой до остальных строк данного ранга максимальна, получит оценку k+(m-1)/m.

Строка со второй по величине суммой расстояний получит оценку k+(m-2)/m. Строка с минимальной суммой расстояний до остальных особей данного ранга будет иметь оценку k.

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

4-й этап. Отбор(селекция).

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

5-й этап. Скрещивание и мутация.

Для создания новых особей-потомков может использоваться любая стандартная мутация и любой из классических операторов скрещивания (одноточечный, двухточечный, равномерный кроссовер), дополненные процедурой исправления недопустимых решений. Недопустимыми решения могут оказаться только за счет невыполнения ограничения. Это можно подкорректировать, исправив несколько координат в соответствующей строке (например, случайным образом значение 3 исправить на 2 или 1, либо значение 1 исправить на 2) . Такие исправления позволят уменьшить левую часть этого ограничения. Они проводятся до тех пор, пока это ограничение не будет выполнено.

6-й этап. Критерий прекращения работы.

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



Глава 6. Разработка приложения

6.1 Требования к приложению

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

Данное приложение должно так же позволять получить точное решение (множество всех оптимальных по Парето точек) данной задачи.

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

Данное приложение должно адекватно реагировать на некорректные данные и выводить соответствующие сообщения.

Данное приложение должно быть совместимо с операционными системами Windows XP\Vista\7.

6.2 Особенности реализации

Для реализации данного приложения была выбрана программная среда Embarcadero RAD Studio 2010. Язык программирования - Delphi. Выбор основан на том, что данная среда имеет все необходимые визуальные компоненты, а язык обеспечивает простую работу с динамическими массивами.

Программа состоит из двух модулей. Unit1 содержит обработчики кнопок. Unit2 отвечает за реализацию генетического алгоритма.

При написании программы применялись как процедурный подход (реализация генетических алгоритмов), так и подход ООП (визуальные компоненты).

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

6.3 Графический интерфейс

На рис.4 представлен графический интерфейс приложения.

Рис.4. Графический интерфейс.

6.4 Тестирование приложения, определение оптимальных параметров

Путем многократного запуска программы и сравнения результатов было установлено, что рекомендуемые параметры программы:

· Количество особей: 50 (увеличение не дает улучшения результата, однако оказывает значительное влияние на скорость выполнения алгоритма).

· Вероятность мутации: <0,1 (увеличение данного значения ухудшает качество получаемого множества ответов, а также замедляет алгоритм). На рис. 5 видно, как решения, получаемые при больших значениях вероятности мутации, заметно отличаются от истинного оптимального множества решений.

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

· Вероятность скрещивания: <0,7 (изменения в сторону увеличения и изменения не дают сильного эффекта, однако использование критических значений, близких к 0 или 1 нежелательно).

· Количество оптимальных решений: определяется пользователем. Чем больше данный параметр, тем разнообразнее множество ответов.

Далее приведена сравнительная таблица времени работы генетического алгоритма и перебора:

Таблица 1 - Время работы в зависимости от размерности задачи.

Кол-во элементов	Время перебора	Время работы генетического алгоритма
100		00:00:10:288
19		00:00:02:496
18		00:00:01:956
17		00:00:01:766
16		00:00:01:756
15		00:00:01:683
14		00:00:01:432
13		00:00:01:233
12	00:01:04:409	00:00:01:204
11	00:00:46:573	00:00:01:054
10	00:00:06:226	00:00:00:543
9	00:00:00:943	00:00:00:466
8	00:00:00:255	00:00:00:474
7	00:00:00:33	00:00:00:471
6	00:00:00:05	00:00:00:492

Время перебора, начиная с 13 элементов, не было рассчитано, т.к. оно требовало слишком больших временных затрат. Тем не менее, общая динамика роста времени хорошо прослеживается. Далее для наглядности приведен график зависимости времени выполнения алгоритмов от размерности задачи, построенный по данной таблице.

Из графика и таблицы видно, что генетический алгоритм слабо зависит от размерности задачи.

Приведем ниже несколько примеров работы программы с рекомендуемыми параметрами.



Рис.6. Примеры работы программы с рекомендуемыми параметрами.

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

Заключение

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



Список использованных источников

1. Половко А.М., Гуров С.В. Основы теории надежности / СПб.: БХВ-Петербург, 2008.

2. Испытания жидкостных ракетных двигателей. Учеб. пособие для авиац. специальностей вузов под. ред. В.З.Левина - М.:Машиностроение, 1981.

3. Львович Я. Е., Каширина И. Л., Генетический алгоритм решения многокритериальной задачи повышения надежности резервирования.

4. Каширина И.Л. Введение в эволюционное моделирование / Воронеж, 2007.



Приложение А. Листинг программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Unit2, TeEngine, ExtCtrls, TeeProcs, Chart, Series,

BubbleCh, Math;

const

ColCount = 4;

MaxRefreshNum = 100;

type

TForm1 = class(TForm)

Edit_N: TEdit;

Label_N: TLabel;

StringGrid1: TStringGrid;

Button1: TButton;

Memo1: TMemo;

Button3: TButton;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Edit_L: TEdit;

Edit_Pmut: TEdit;

Edit_Pcross: TEdit;

Label4: TLabel;

Edit_RecQuantity: TEdit;

Chart1: TChart;

Series2: TPointSeries;

Button2: TButton;

Series1: TPointSeries;

procedure FormCreate(Sender: TObject);

procedure Edit_NChange(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure FormResize(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

time1, time2: TDateTime;

implementation

{$R *.dfm}

procedure InitInputData;

var i,j: integer;

begin

//Проверка введенных данных на корректность и инициализация

try

InitInputArrays;

RecQuantity := StrToInt (Form1.Edit_RecQuantity.Text);

L := StrToInt (Form1.Edit_L.Text);

Pmut := StrToFloat (Form1.Edit_Pmut.Text);

Pcros := StrToFloat (Form1.Edit_Pcross.Text);

if (Pmut < 0) or (Pmut > 1) or (Pcros < 0) or (Pcros > 1) then

begin

EraseInputArrays;

ShowMessage ('Данные некорректны');

exit;

end;

for i := 1 to N do

begin

P[i-1] := StrToFloat(Form1.StringGrid1.Cells[1,i]);

T[i-1] := StrToFloat(Form1.StringGrid1.Cells[2,i]);

S[i-1] := StrToFloat(Form1.StringGrid1.Cells[3,i]);

G[i-1] := StrToFloat(Form1.StringGrid1.Cells[4,i]);

if (P[i-1]<0) or (P[i-1]>1) or (G[i-1]<1) or (T[i-1]<=0) then

begin

EraseInputArrays;

ShowMessage ('Значения P, G или T введены некорректно');

exit;

end;

end;

except

EraseInputArrays;

ShowMessage ('Введены некорректные данные');

exit;

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

var i,j,k: integer;

Str: string;

begin

time1 := now;

randomize;

InitInputData;

//Создание начальной популяции

RefreshNum := 0;

InitRec;

InitTAvg;

InitPopulation (Population);

InitPopulation (TempPopulation);

InitPopulation (TempPopulationCrossed);

InitRecord;

RankPopulation (Population);

AddToRecord (Population);

//ГА

REPEAT

SelectPopulation(Population, TempPopulation);

CrossPopulation (TempPopulation,TempPopulationCrossed);

MutantPopulation (TempPopulationCrossed);

FixPopulation (TempPopulationCrossed);

CountFitness (TempPopulationCrossed);

CopyPopulation (TempPopulationCrossed, Population);

RankPopulation (Population);

AddToRecord (Population);

inc (RefreshNum);

UNTIL RefreshNum = MaxRefreshNum;

time2 := now;

//Вывод результатов

for k := 1 to RecQuantity do

if Rec[k].S <> -9999999 then

begin

memo1.Lines.Add('============================='+IntToStr(k));

memo1.Lines.Add('S='+FloatToStr(-Rec[k].S));

memo1.Lines.Add('P='+FloatToStr(Rec[k].P));

Series2.AddXY(-Rec[k].S, rec[k].P,'',clred);

for i := 0 to Rec[k].Quantity-1 do

begin

str := '';

for j := 0 to N-1 do

str := str + IntTostr(Rec[k].Solutions[i][j]);

memo1.Lines.Add(str);

memo1.Lines.Add(FloatToStr(SumTxX(Rec[k].Solutions[i])))

end;

end;

memo1.Lines.Add('=============================');

//очистка памяти

EraseInputArrays;

EraseRec;

ErasePopulation (Population);

Erasepopulation (TempPopulation);

Erasepopulation (TempPopulationCrossed);

Memo1.Lines.Add ('Время выполнения ген. алгоритма: '+

FormatDateTime('hh:mm:ss:zz', time2-time1));

end;

procedure TForm1.Button2Click(Sender: TObject);

//перебор

const

base = 3; //кол-во вариантов резервирования

type

TSolutionArray = array of Tindivid;

TKrArr = array [1..3] of real; //1 - S, 2 - P, 3 - T

TKrList = array of TKrArr;

var

i,j,k: longint;

max: longint; //3^N

Tavg_1: real; //среднее время

Kr: TKrList; //массив S P T

X: TSolutionArray; //массив x1 x2 ... xN

NotDominated: boolean; //флаг недоминируемости

begin

//инициализация начальных переменных

time1 := now;

InitInputData;

max := round(power(3,N))-1;

SetLength (Kr, max + 1);

SetLength (X, max + 1);

Tavg_1 := 0;

for i := 0 to N-1 do

Tavg_1 := Tavg_1 + 1/T[i];

//задание матрицы всех возможных значений Х

for j := 0 to max do //перебор на основе перевода чисел в троичную систему

begin

//выделение памяти под xj

SetLength(X[j],N);

//перевод числа в троичную систему

k := j;

for i := 0 to N-1 do

begin

X[j][N-i-1] := (k - (k div base) * base) + 1;

k := k div base;

end;

//вычисление значения критериев

Kr[j][1] := -GetS (X[j]);

Kr[j][2] := GetP (X[j]);

Kr[j][3] := SumTxX (X[j]);

end;

//на этот момент мы имеем массив всех комбинаций

//и массив соответствующих значений критерия

//вывести недоминируемые точки

for j := 0 to max do

if (Kr[j][3]<=Tavg_1) then

begin

NotDominated := true;

for i := 0 to max do

if i <> j then

if (((Kr[i][1]>Kr[j][1]) and (Kr[i][2]>=Kr[j][2])) or

((Kr[i][1]>=Kr[j][1]) and (Kr[i][2]>Kr[j][2]))) and (Kr[i][3]<=Tavg_1) then

begin

NotDominated := false;

break;

end;

if NotDominated then

//добавление на график

begin

Series1.AddXY(-Kr[j][1],Kr[j][2],'',clBlue);

end

end;

time2 := now;

EraseInputArrays;

for j := 0 to max do

X[j] := nil;

X := nil;

Kr := nil;

Memo1.Lines.Add ('Время выполнения алгоритма перебора: '+

FormatDateTime('hh:mm:ss:zz', time2-time1));

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

Memo1.Lines.Clear;

Series2.Clear;

Series1.Clear;

end;

procedure TForm1.Edit_NChange(Sender: TObject);

var N_old: integer;

i,j: integer;

begin

if Edit_N.Text <> '' then

begin

N_old := N;

N := StrToInt(Edit_N.Text);

StringGrid1.RowCount := N+1;

for i := N_old+1 to N do

begin

for j := 1 to COlCount do

StringGrid1.Cells[j,i] := '';

StringGrid1.Cells[0,i] := IntToStr(i);

end;

end;

end;

procedure TForm1.FormCreate(Sender: TObject);

var i,j: integer;

begin

N := StrToInt(Edit_N.Text);

StringGrid1.RowCount := N+1;

StringGrid1.Cells[0,0] := ' i';

StringGrid1.Cells[1,0] := ' Pi';

StringGrid1.Cells[2,0] := ' Ti';

StringGrid1.Cells[3,0] := ' Si';

StringGrid1.Cells[4,0] := ' Gi';

for i := 1 to N do

StringGrid1.Cells[0,i] := IntToStr(i);

StringGrid1.ColWidths[0] := 15;

end;

procedure TForm1.FormResize(Sender: TObject);

begin

StringGrid1.Height := Height - 205;

Memo1.Height := Height - 205;

Width := 937;

end;

end.

unit Unit2;

INTERFACE

uses SysUtils;

type

TIndivid = array of 1..3;

TRealArray = array of real;

TFitness = record

S: real;

P: real

end;

TIndividArray = array of TIndivid;

TFitnessArray = array of TFitness;

TPopulation = record

Individs: TIndividArray;

Fitness: TFitnessArray;

Rank: TRealArray;

end;

TEuc = record

index: integer;

distance: real;

valuation: real

end;

TEucArray = array of TEuc;

TRecElement = record

S: real;

P: real;

Solutions: TIndividArray;

Quantity: integer;

end;

TRecord = array of TRecElement;

var

//Individ: TIndivid;

Population: TPopulation; //начальная популяция

TempPopulation: TPopulation; //временная популяция

TempPopulationCrossed: TPopulation; //временная популяция потомков

//NewPopulation: TPopulation;

P,T,S,G: TRealArray; //массивы входных данных

N,L: integer; //длина хромосомы и кол-во особей соот-но

Pmut: real;//вероятность мутации

Pcros: real;//вероятность скрещивания

Tavg: real; //ср время

Rec: TRecord; //рекордное множество

RecQuantity: integer; //количество рекордных решений

RefreshNum: integer; //кол-во обновлений

procedure InitPopulation (var Pop: TPopulation);

//создание начальной популяции, состоящей из L особей длины N

procedure ErasePopulation (var Pop: TPopulation);

//удаление популяции

procedure RankPopulation (var Pop: TPopulation);

//ранжирование индивидов в популяции

procedure CountFitness (var Pop: TPopulation);

//вычисление значений целевых функций

procedure SelectPopulation (var Pop: TPopulation; var tempPop: TPopulation);

//формирование временной популяции выбором из двух

procedure SelectPopulation2 (var Pop: TPopulation; var tempPop: TPopulation);

//формирование временной популяции выбором из трех

procedure CrossPopulation (var TempPop: TPopulation; var TempPopCr: TPopulation);

//скрещивание индивидов популяции

procedure MutantPopulation (var TempPop: TPopulation);

//мутация популяции

procedure FixPopulation (var TempPop: TPopulation);

//исправление популяции

procedure InitTavg;

//вычисление T-среднего

function SumTxX (var Indiv: TIndivid): real;

//вычисление левой части ограничения по времени

procedure InitRecord;

//задание рекордного массива начальными числами

procedure AddToRecord (var TempPop: TPopulation);

//изменение рекордного множества при появлении новой популяции

procedure CopyPopulation (var PopFrom: TPopulation; var PopInto: TPopulation);

//копирование популяций

procedure InitRec;

//инициализация рекордного множества

procedure EraseRec;

//удаление рекордного множества

procedure InitInputArrays;

//инициализация входных массивов

procedure EraseInputArrays;

//удаление входных массивов

function GetS (var II: TIndivid): real;

//определение стоимости по решению

function GetP (var II: TIndivid): real;

//определение вероятности по решению

IMPLEMENTATION

function GetS (var II: TIndivid): real;

var j: integer;

begin

result := 0;

for j := 0 to N-1 do

case II[j] of

1: result := result + S[j];

2: result := result + 2 * S[j] * G[j];

3: result := result + 4 * S[j];

end;

end;

function GetP (var II: TIndivid): real;

var j: integer;

begin

result := 1;

for j := 0 to N-1 do

case II[j] of

1: result := result * P[j];

2: result := result * (2*P[j]-P[j]*P[j]);

3: result := result * (3*P[j]*P[j]-2*P[j]*P[j]*P[j]);

end;

end;

procedure CountFitness (var Pop: TPopulation);

var i,j: integer;

begin

for i := 0 to L-1 do

begin

Pop.Fitness[i].S := -GetS(Pop.Individs[i]);

Pop.Fitness[i].P := GetP(Pop.Individs[i]);

end;

end;

procedure InitPopulation (var Pop: TPopulation);

var i,j: integer;

begin

//randomize; //задаем длину

SetLength(Pop.Individs, L);

SetLength(Pop.Fitness, L);

SetLength(Pop.Rank, L);

//присваиваем случайные значения

for i := 0 to L-1 do

begin

SetLength(Pop.Individs[i],N);

for j := 0 to N-1 do

Pop.Individs[i][j] := random(3)+1;

end;

//исправляем популяцию

FixPopulation(Pop);

//вычисляем значения целевых функций

CountFitness(Pop);

for i := 0 to L-1 do //а нужно ли??

Pop.Rank[i] := 0;

end;

procedure ErasePopulation (var Pop: TPopulation);

var i,j: integer;

begin

for i := 0 to L-1 do

begin

Pop.Individs[i] := nil

end;

Pop.Individs := nil;

Pop.Fitness := nil;

Pop.Rank := nil;

end;

procedure Sort(var Euc: TEucArray; p,q : integer); {p,q -- индексы начала и конца сортируемой части массива}

Var i,j : integer;

r,T: real;

Begin

if p<q then {массив из одного элемента тривиально упорядочен}

begin

r:=Euc[p].distance;

i:=p-1;

j:=q+1;

while i<j do

begin

repeat

i:=i+1;

until Euc[i].distance>=r;

repeat

j:=j-1;

until Euc[j].distance<=r;

if i<j then

begin

T:=Euc[i].distance;

Euc[i].distance:=Euc[j].distance;

Euc[j].distance:=T;

end;

end;

Sort(Euc,p,j);

Sort(Euc,j+1,q);

end;

End;

function IndivIsNotDominated (var Pop: TPopulation; index: integer; str: string): boolean;

var k: integer;

begin

result := true;

for k :=0 to L-1 do

if (index <> k) and (pos(' ' + IntToStr(k) + ' ',str)=0) then

if (Pop.Fitness[index].S<=Pop.Fitness[k].S) and (Pop.Fitness[index].P <= Pop.Fitness[k].P) and

((Pop.Fitness[index].S<Pop.Fitness[k].S) or (Pop.Fitness[index].P < Pop.Fitness[k].P))then

begin

result := false;

exit

end

end;

procedure RankPopulation (var Pop: TPopulation);

var Scur, Stotal: string;

r: integer;

i: integer;

MaxRank: integer;

m: integer;

EucArr: TEucArray;

k: integer;

t: integer;

NumsinStr: integer;

begin

for i := 0 to L-1 do

begin

Pop.Fitness[i].S := -GetS(Pop.Individs[i]);

Pop.Fitness[i].P := GetP(Pop.Individs[i]);

Pop.Rank[i] := 0;

end;

Stotal := ' ';

r := 1;

repeat

//выбрать недоминируемые элементы и присвоить им ранг

NumsInStr := 0;

Scur := ' ';

for i := 0 to L-1 do

if pos(' '+IntToStr(i)+' ',Stotal)=0 then

if IndivIsNotDominated(Pop, i, Stotal) then

begin

Scur := Scur + IntToStr(i) + ' ';

Pop.Rank[i] := r;

inc(NumsInStr);

end;

//m := length(Scur); //создаем массив текущего ранга !!!!!!!!!!!!!

m := NumsInStr;

SetLength(EucArr, m);

t := 0;

for k := 0 to L-1 do

if pos(' '+inttostr(k)+' ',Scur)<>0 then

begin

EucArr[t].index := k;

inc(t);

end;

for k := 0 to m-1 do //считаем расстрояния

begin

EucArr[k].distance := 0;

for t := 0 to m-1 do

EucArr[k].distance := EucArr[k].distance +

sqrt(sqr(Pop.Fitness[EucArr[k].index].S-Pop.Fitness[EucArr[t].index].S) +

sqr(Pop.Fitness[EucArr[k].index].P-Pop.Fitness[EucArr[t].index].P));

end;

Sort(EucArr, 0, m-1); //сортируем

for k := 0 to m-1 do

Pop.Rank[EucArr[k].index] := r +(m-k-1)/m; //записываем ранки

EucArr := nil; //удаляем массив

Stotal := Stotal + Scur;

inc(r);

until

(length(Scur)=1) or (r>L+2);

//после этого r - maxrank

//преобразовываем ранг

for i:= 0 to L-1 do

Pop.Rank[i] := r + Pop.Rank[i] - 2 * trunc(Pop.Rank[i]) - 1;

end;

procedure SelectPopulation (var Pop: TPopulation; var TempPop: TPopulation);

var i,j: integer;

t1, t2: integer; //индексы выбранных особей

begin

for i := 0 to L-1 do

begin

t1 := random (L);

t2 := random (L);

if Pop.Rank[t1] >= Pop.Rank[t2] then

begin

for j := 0 to N-1 do

TempPop.Individs[i][j] := Pop.Individs[t1][j];

TempPop.Fitness[i].S := pop.Fitness[t1].S;

TempPop.Fitness[i].P := Pop.Fitness[t1].P;

TempPop.Rank[i] := Pop.Rank[t1]

end

else

begin

for j := 0 to N-1 do

TempPop.Individs[i][j] := Pop.Individs[t2][j];

TempPop.Fitness[i].S := pop.Fitness[t2].S;

TempPop.Fitness[i].P := Pop.Fitness[t2].P;

TempPop.Rank[i] := Pop.Rank[t2]

end;

end;

end;

procedure SelectPopulation2 (var Pop: TPopulation; var tempPop: TPopulation);

var i,j: integer;

t1, t2, t3: integer; //индексы выбранных особей

begin

for i := 0 to L-1 do

begin

t1 := random (L);

t2 := random (L);

t3 := random (L);

if (Pop.Rank[t1] >= Pop.Rank[t2]) and (Pop.Rank[t1] >= Pop.Rank[t3]) then

begin

for j := 0 to N-1 do

TempPop.Individs[i][j] := Pop.Individs[t1][j];

TempPop.Fitness[i].S := pop.Fitness[t1].S;

TempPop.Fitness[i].P := Pop.Fitness[t1].P;

TempPop.Rank[i] := Pop.Rank[t1]

end

else

if (Pop.Rank[t2] >= Pop.Rank[t1]) and (Pop.Rank[t2] >= Pop.Rank[t3]) then

begin

for j := 0 to N-1 do

TempPop.Individs[i][j] := Pop.Individs[t2][j];

TempPop.Fitness[i].S := pop.Fitness[t2].S;

TempPop.Fitness[i].P := Pop.Fitness[t2].P;

TempPop.Rank[i] := Pop.Rank[t2]

end

else

begin

for j := 0 to N-1 do

TempPop.Individs[i][j] := Pop.Individs[t3][j];

TempPop.Fitness[i].S := pop.Fitness[t3].S;

TempPop.Fitness[i].P := Pop.Fitness[t3].P;

TempPop.Rank[i] := Pop.Rank[t3]

end

end;

end;

procedure CrossPopulation (var TempPop: TPopulation; var TempPopCr: TPopulation);

var i,j: integer;

t1, t2: integer;

CrPt: integer;//crossover point

temp: 1..3;

begin

{for i := 0 to (L div 2) do

if random(101)/100 <= Pcros then

begin

t1 := random (L);

t2 := random (L);

for j := CrPt to N-1 do

begin

temp := TempPop.Individs[t1][j];

TempPop.Individs[t1][j] := TempPop.Individs[t2][j];

TempPop.Individs[t2][j] := temp;

end;

end; }