Мочалов Системы поддержки принятия решений в медицине. В настоящее время задача повышения качества оказываемой медицинской помощи и жизни населения в целом является одной из наиболее сложных и значимых
 Скачать 0.91 Mb.
|
1 2 Введение В настоящее время задача повышения качества оказываемой медицинской помощи и жизни населения в целом является одной из наиболее сложных и значимых. Основные показатели здоровья нации (такие как средняя продолжительность жизни населения, стоимость медицинского обслуживания) напрямую связаны не только с факторами социального характера (удорожание лечения из-за внедрения новых технологий, недостаточное финансирование отрасли, увеличение количества заболеваний и др.), но и с качеством оказываемой медицинской помощи. Повышение эффективности использования ресурсов здравоохранения за счет внедрения современных информационных технологий, а также повышение доступности и качества медицинской помощи, оказываемой населению в целом, являются глобальными тенденциями развития электронного здравоохранения в мире (E-Health) и были озвучены в ходе крупнейшего международного форума посвященного вопросам использования ИКТ в здравоохранении – Global E-Health Forum, приходившего в октябре 2010 года в городе Гамбург, Германия [1]. Обозначенные проблемы в той или иной степени характерны практически для всех стран (не исключая развитые страны). Например, в докладе Института медицины США указано, что системе здравоохранения США не удается обеспечить высококачественную медицинскую помощь всем гражданам. Согласно статистическим данным, даже в такой высокоразвитой стране как США более 100 тыс. граждан ежегодно погибает вследствие медицинских ошибок, которые можно было бы предотвратить. Между тем, врачебные ошибки в большинстве случаев отнюдь не являются следствием злого умысла, безответственности или низкой квалификации медиков. По данным исследований бостонской клиники Brigham and Women’s Hospital, сегодня в мире насчитывается более 10 тыс. заболеваний, свыше 3 тыс. лекарственных препаратов, 300 различных радиологических процедур и 1 тыс. лабораторных исследований. В выступлении заместителя директора информационно-аналитического центра Российской Академии медицинских наук, доктора технических наук Андрей Столбова приведены данные о 4 тыс. активно использующихся в мире медикаментах, среди которых зафиксировано более 2 тыс. взаимодействий, существенным образом влияющих на возможности их применения при том или ином заболевании. Само собой разумеется, что держать в голове такой объем информации совершенно невозможно. Кроме того, с учетом того, что решения зачастую должны приниматься в условиях цейтнота, а также принимая во внимание высокую стоимость каждой ошибки (поскольку речь идет о лечении пациентов), проблема обеспечения врачей современными средствами поддержки принятия решений становится все более актуальной. Поэтому во многих европейских странах основные акценты в настоящее время делаются на информационную поддержку врача, на создание новой информационной среды его деятельности, потому что именно это позволяет повысить качество лечения и его доступность. За рубежом распространена практика, когда в больницах практикующие врачи еженедельно собираются с коллегами и обсуждают сложные случаи лечения пациентов. При этом в процессе принятия решения о лечении пациента используются два основных источника информации: во-первых, это утвержденные клинические рекомендации, с которыми сверяются клинические случаи пациентов, а, во-вторых, истории заболеваний пациентов с аналогичными симптомами, которые были вылечены ранее. Для решения данных задач должны использоваться системы поддержки принятия решений. Основные недостатки существующих систем поддержки принятия решений Используемые в настоящий момент традиционные системы поддержки принятия решений, основанные на правилах, не способны обеспечить понимание «семантики» медицинских данных и клинических рекомендаций и на практике демонстрируют ряд существенных «ограничений». Основными недостатками большинства из этих систем являются:
История систем поддержки принятия решения Теоретические исследования в области разработки первых систем поддержки принятия решений проводились в технологическом институте Карнеги в конце 50-х начале 60-х годов XX века. Объединить теорию с практикой удалось специалистам из Массачусетского технологического института в 60-х годах. В середине и конце 80-х годов XX столетия стали появляться такие системы, как EIS, GDSS, ODSS. В 1987 году компания Texas Instruments разработала для United Airlines Gate Assignment Display System. Это позволило значительно снизить убытки от полетов и отрегулировать управление различными аэропортами, начиная от Международного аэропорта O’Hare в Чикаго и заканчивая Stapleton в Денвере, штат Колорадо. В 90-х годах сфера возможностей СППР расширялась благодаря внедрению хранилищ данных и инструментов OLAP. Появление новых технологий отчетности сделало СППР незаменимой в менеджменте [3]. Система поддержки принятия решений (СППР) — компьютерная автоматизированная система, целью которой является помощь людям, принимающим решение в сложных условиях, для полного и объективного анализа предметной деятельности. Для анализа и выработок предположений в СППР используются разные методы: информационный поиск интеллектуальный анализ данных, поиск значений в базах данных, рассуждение на основе прецедентов, имитационное моделирование эволюционные вычисление и генетические алгоритмы нейронные сети, ситуационный анализ, коллективное моделирование, методы искусственного интеллекта. Генетические алгоритмы Генетический алгоритм был предложен более 20 лет назад Джоном Холландом. Генетический алгоритм реализует метод случайного поиска по аналогии с теорией эволюции Дарвина. Основан на естественном отборе — основном механизме эволюции, работающем по принципу «выживает наиболее приспособленный». Подражая этому процессу, генетический алгоритм дает возможность находить близкие к оптимальным решения задачи. Суть алгоритма. Алгоритм управляет набором представителей, которые могут рассматриваться как возможные решения поставленной задачи. Отобранные на каждом шаге лучшие представители перемешиваются («скрещиваются») между собой, производя «мутантов». От полученных таким образом новых представителей ожидают еще более хороших результатов. Процесс повторятся несколько раз пока не будет достигнуто целевое значение. Достоинства применения алгоритма: 1. применяется для решения сложных неформализованных задач, для которых не разработано специальных методов; 2. имеет преимущества перед другими алгоритмами при очень больших размерах задач и отсутствия упорядоченности в исходных данных; 3. алгоритм выполняется существенно быстрее других алгоритмов поиска на большом пространстве значений и значительно экономит память компьютера. Недостатки алгоритма: 1. генетический алгоритм не гарантирует, что найденное решение будет оптимальным (приемлем для поиска «достаточно хорошего» решения задачи за «достаточно короткое время»); 2. в случаях, когда задача может быть решена специально разработанным для неё методом, практически всегда такие методы будут эффективнее генетического алгоритма как по быстродействию, так и по точности найденных решений; 3. неэффективен на небольшом пространстве поиска. Имитационное моделирование Имитационный подход к построению СППР основан на многоэтапной процедуре принятия решения, включающей этапы: 1. выявление структурных особенностей в поступаемых в ходе мониторинга данных с применением концепции Хранилища данных и анализа тенденций; 2. визуализация выявленных в данных зависимостей с помощью средств интеллектуального анализа данных и OLAP-технологий. Основой процедуры принятия решений в таких системах выступает обобщённая модель объекта исследования, реализуемая в СППР на основе комплекса взаимосвязанных имитационных и оптимизационных моделей с развитыми динамическими и информационными связями между моделями всех уровней. Эксперт активно участвует в процессе принятия решения: детализирует проблему и модель, осуществляет генерацию альтернатив, постановку направленного вычислительного эксперимента на имитационной модели, выбор и ранжирование критериев. Кроме того, технология имитационного моделирования позволяет учитывать субъективные предпочтения эксперта и его опыт в вопросе принятия решения. Достоинства имитационного моделирования: 1. имитационная модель позволяет точно и адекватно описать моделируемый процесс; 2. имитационная модель обладает гибкостью варьирования структуры, алгоритмов и параметров системы. Недостатки имитационного моделирования: 1. решение, полученное на имитационной модели, всегда носит частный характер, так как оно соответствует фиксированным элементам структуры, алгоритмам поведения и значениями параметров системы; 2. большие трудозатраты на создание модели и проведение экспериментов, а также обработку результатов. Когнитивное моделирование Системы, для которых характерны многоаспектность происходящих в них процессов и их взаимосвязанность, отсутствие достаточной количественной информации о динамике процессов, а также изменчивость характера процессов во времени, принято считать слабоструктурированными. Такие системы с успехом строятся с использованием средств когнитивного моделирования. В рамках когнитивной модели информация о системе представляется в виде набора понятий и связывающей их причинно-следственной сети, называемой когнитивной картой, которая является отражением субъективных представлений эксперта о законах и закономерностях, присущих моделируемой системе. К когнитивной карте применяются методы аналитической обработки, ориентированные на исследование структуры системы и получение прогнозов её поведения при различных управляющих воздействиях, с целью синтеза эффективных стратегий управления. Недостатки когнитивного моделирования: 1. ограниченность применения; 2. невозможность численного моделирования поведения систем, так как результаты получаются качественными. Рассуждение на основе прецедентов Применение метода для решения задач оправдано в случае выполнения следующих условий: 1. подобные задачи должны иметь подобные решения (принцип регулярности); 2. виды задач, с которыми сталкивается решатель, должны иметь тенденции к повторению. Основной целью использования аппарата прецедентов в СППР является выдача готового решения ЛПР для текущей ситуации на основе прецедентов, которые уже имели место в прошлом при управлении данным объектом или процессом. Суть метода Поиск решения на основе прецедентов заключается в определении степени сходства текущей ситуации с ситуациями прецедентов из базы правил (БП). При этом учитываются веса параметров для ситуации из БП, заданные экспертом. Степень сходства зависит от близости текущей ситуации к ситуации прецедента. Рассуждение на основе прецедентов может не привести к необходимому решению возникшей проблемной ситуации, например, в случае отсутствия подобной ситуации в БП. Поэтому необходимо предусмотреть пополнение БП в процессе рассуждения (вывода) [4]. К преимуществам рассуждений на основе прецедентов можно отнести следующие аспекты: 1. возможность напрямую использовать опыт, накопленный системой без интенсивного привлечения эксперта в той или иной предметной области; 2. возможность сокращения времени поиска решения поставленной задачи за счет использования уже имеющегося решения для подобной задачи; 3. существует возможность исключить повторное получение ошибочного решения; 4. отсутствует необходимость полного и углубленного рассмотрения знаний о конкретной предметной области; 5. возможно применение эвристик, повышающих эффективность решения задач. К недостаткам рассуждений на основе прецедентов можно отнести следующее: 1. при описании прецедентов обычно ограничиваются поверхностными знаниями о предметной области; 2. большое количество прецедентов может привести к снижению производительности системы; 3. проблематичным является определение критериев для индексации и сравнения прецедентов; 4. проблемы с отладкой алгоритмов определения подобных (аналогичных) прецедентов; 5. невозможность получения решения задач, для которых нет прецедентов или степень их сходства (подобия) меньше заданного порогового значения [4]. Нейронные сети и системы с нечёткой логикой Нейронные сети привлекательны с интуитивной точки зрения, так как они основаны на примитивной биологической модели нервных систем. Нейронные сети вошли в практику везде, где нужно решать задачи прогнозирования, классификации или управления. Это обусловлено тем, что во-первых, нейронные сети позволяют воспроизводить чрезвычайно сложные зависимости. Кроме того, нейронные сети справляются с большим числом переменных. Во-вторых, простотой использования. Нейронные сети учатся на примерах. Пользователь нейронной сети подбирает представительные данные, а затем запускает алгоритм обучения, который автоматически воспринимает структуру данных. При этом от пользователя, конечно, требуется какой-то набор эвристических знаний о том, как следует отбирать и подготавливать данные, выбирать нужную архитектуру сети и интерпретировать результаты, однако уровень знаний, необходимый для успешного применения нейронных сетей, гораздо скромнее, чем при использовании традиционных методов. Нейронные сети хороши для задач распознавания образов, но весьма неудобны для объяснения, как они такое распознавание осуществляют. Они могут автоматически приобретать знания, но процесс их обучения зачастую происходит достаточно медленно, а анализ обученной сети весьма сложен (обученная сеть представляет обычно черный ящик для пользователя). При этом какую-либо априорную информацию (знания эксперта) для ускорения процесса ее обучения в нейронную сеть ввести невозможно. Системы с нечеткой логикой, напротив, хороши для объяснения получаемых с их помощью выводов, но они не могут автоматически приобретать знания для использования их в механизмах выводов. Необходимость разбиения универсальных множеств на отдельные области, как правило, ограничивает количество входных переменных в таких системах небольшим значением. Системы с нечеткой логикой целесообразно применять в следующих случаях: 1. для сложных процессов, когда нет простой математической модели; 2. если экспертные знания об объекте или о процессе можно сформулировать только в лингвистической форме. Системы, базирующиеся на нечеткой логике, применять нецелесообразно: 1. если требуемый результат может быть получен каким-либо другим (стандартным) путем; 2. когда для объекта или процесса уже найдена адекватная и легко исследуемая математическая модель. Отметим, что основными недостатками систем с нечеткой логикой являются следующие: 1. исходный набор постулируемых нечетких правил формулируется экспертом-человеком и может оказаться неполным или противоречивым; 2. вид и параметры функций принадлежности, описывающих входные и выходные переменные системы, выбираются субъективно и могут оказаться не вполне отражающими реальную действительность. Перспективно применение в СППР комбинированных методов принятия решений в сочетании с методами искусственного интеллекта и компьютерным моделированием [5]. Генетические алгоритмы Генетический алгоритм представляет собой метод, отражающий естественно эволюцию методов решения проблем, в первую очередь задач оптимизации. Генетические алгоритмы – это процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частности, генетические алгоритмы [6]:
Перечисленные четыре свойства, которые можно сформулировать также как кодирование параметров, операции на популяциях, использование минимума информации о задаче и рандомизация операций приводят в результате к устойчивости генетических алгоритмов и к их превосходству над другими широко применяемыми технологиями. Основные понятия генетических алгоритмов При описании генетических алгоритмов используется определения, заимствованные из генетики. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген, хромосома, генотип, фенотип, аллель. Также используются соответствующие этим терминам определения из технического лексикона, в частности, цепь, двоичная последовательность, структура. Популяция – это конечное множество особей. Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированным в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами. Хромосомы (другие названия – цепочки или кодовые последовательности) – это упорядоченные последовательности генов. Ген (также называемый свойством, знаком или детектором) – это атомарный элемент генотипа, в частности, хромосомы. Генотип или структура – это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы). Фенотип – это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска). Аллель – это значение конкретного гена, также определяемое как значение свойства или вариант свойства. Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов – это локи. Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitnessfunction), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точно и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, минимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр – стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации. Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое пополнение» или «поколение потомков». Классический генетический алгоритм Основной (классический) генетический алгоритм (также называемый элементарным или простым генетически алгоритмом) состоит из следующих шагов:
Блок-схема основного генетического алгоритма изображена на рисунке 1. Рассмотрим конкретные этапы этого алгоритма более подробно с использованием дополнительных подробностей, представленных на рисунке 2. Инициализация, т.е. формирование исходной популяции, заключается в случайном выборе заданного количества хромосом (особей), представляемых двоичными последовательностями фиксированной длины. Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение этой функции, тем выше «качество» хромосомы. Форма функции приспособленности зависит от характера решаемой задачи. Предполагается, что функция приспособленности всегда принимает неотрицательные значения и, кроме того, что для решения оптимизационной задачи требуется максимизировать эту функцию. Если исходная форма функции приспособленности не удовлетворяет этим условиям, то выполняется соответствующее преобразование (например, задачу минимизации функции можно легко свести к задаче максимизации). Проверка условия остановки алгоритма. Определение условия остановки генетического алгоритма зависит от его конкретного применения. В оптимизационных задачах, если известно максимальное (или минимальное) значение функции приспособленности, то остановка алгоритма может произойти после достижения ожидаемого оптимального значения, возможно – с заданной точностью. Остановка алгоритма может произойти после достижения ожидаемого оптимального значения, возможно – с заданной точностью. Остановка алгоритма также может произойти в случае, когда его выполнение не приводит к улучшению уже достигнутого значения. Алгоритм может быть остановлен по истечении определенного времени выполнения либо после выполнения заданного количества итераций. Если условие остановки выполнено, то производится переход к завершающему этапу выбора «наилучшей» хромосомы. В противном случае на следующем шаге выполняется селекция.  Рисунок 1. Блок-схема генетического алгоритма Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут учувствовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки (roulette wheel selection), который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует суме значений функции приспособленности всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой  для  (где  обозначает численность популяции) соответствует сектор колеса  ), выраженный в процентах согласно формуле:  Причем  – значение функции приспособленности хромосомы , а  – вероятность селекции хромосомы . Селекция хромосомы может быть представлена как результат поворота колеса рулетки поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор хромосомы можно отождествить с выбором числа из интервала [a, b], где a и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что 0 a b 100. В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса.В результате процесса селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью N, равной численности текущей популяции. Применение генетических операторов к хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской популяции. В классическом генетическом алгоритме применяются два основных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation). Однако следует отметить, что оператор мутации играет явно второстепенную роль по сравнению с оператором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация – достаточно редко. Вероятность скрещивания, как правило, достаточно велика (обычно  ), тогда как вероятность мутации устанавливается весьма малой (чаще всего  ). Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко.В генетическом алгоритме мутация хромосом может выполняться на популяции родителей перед скрещиванием либо на популяции потомков, образованных в результате скрещивания. Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания  . Далее для каждой пары отобранных таки образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосом каждого из родителей состоит из L генов, то очевидно, что точка скрещивания  представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L-1]. В результате скрещивания пары родительских хромосом получается следующая пара потомков:
Оператор мутации с вероятностью  изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или обратно). Например, если в хромосоме [100110101010] мутации подвергается ген на позиции 7, то его значение, равное 1, изменяется на 0, что приводит к образованию хромосомы [100110001010]. Как уже упоминалось выше, вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность мутации может эмулироваться, например, случайным выбором числа из интервала [0, 1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению .Формирование новой популяции. Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включаются в состав новой популяции. Она становится так называемой текущей популяцией для данной итерации генетического алгоритма. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом этой популяции, после чего проверяется условие остановки алгоритма и либо фиксируется результат в виде хромосомы с наибольшим значением функции приспособленности. Либо осуществляется переход к следующему шагу генетического алгоритма, т.е. к селекции. В классическом генетическом алгоритме вся предшествующая популяция хромосом замещается новой популяцией потомков. Имеющей ту же численность. Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности. В завершение следует признать, что генетические алгоритмы унаследовали свойства естественного эволюционного процесса, состоящие в генетических изменениях популяций организмов с течением времени. Главный фактор эволюции – это естественный отбор (т.е. природная селекция), который приводит к тому, что среди генетически различающихся особей одной и той же популяции выживают и оставляют потомство только наиболее приспособленные к окружающей среде. В генетических алгоритмах также выделяется этап селекции, на котором из текущей популяции выбираются и включаются в родительскую популяцию особи, имеющие наибольшие значения функции приспособленности. На следующем этапе, который иногда называется эволюцией, применяются генетические операторы скрещивания и мутации, выполняющие рекомбинацию генов в хромосомах. Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным образом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности . Например, если в качестве родителей случайным образом выбираются две хромосомы из родительской популяции численностью , то  . Аналогично, если из родительской популяции численностью выбирается 2z хромосом ( ), которые образуют z пар родителей, то  . Обратим внимание, что если все хромосомы текущей популяции объединены в пары до скрещивания, то  . После операции скрещивания родители в родительской популяции замещаются их потомками.Операция мутации изменяет значения генов в хромосомах с заданной вероятностью способом, представленным при описании соответствующего оператора. Это приводит к инвертированию значений отобранных генов с 0 на 1 и обратно. Значение , как правило, очень мало, поэтому мутации подвергается лишь небольшое количество генов. Скрещивание – это ключевой оператор генетических алгоритмов, определяющий их возможности и эффективность. Мутация играет более ограниченную роль. Она вводит в популяцию некоторое разнообразие и предупреждает потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания.Основной (классический) генетический алгоритм известен в литературе в качестве инструмента, в котором выделяются три вида операций: репродукции, скрещивания и мутации. Термины селекция и репродукция в данном контексте используются в качестве синонимов. При этом репродукция в данном случае связывается скорее с созданием копий хромосом родительского пула, тогда как более распространенное содержание этого понятия обозначает процесс формирования новых особей, происходящих от конкретных родителей. Выполнение классического генетического алгоритма Рассмотрим сильно упрощенный и довольно искусственный пример, состоящий в нахождении хромосомы с максимальным количеством единиц. Допустим, что хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц. Посмотрим, как протекает процесс решения этой весьма тривиальной задачи с помощью генетического алгоритма. Инициализация, или выбор исходной популяции хромосом. Необходимо случайным образом сгенерировать 8 двоичных последовательностей длиной 12 битов. Это можно достигнуть, например, подбрасывание монеты (96 раз, при выпадении «орла» приписывается значение 1, а в случае «решки» - 0). Таким образом можно сформировать исходную популяцию     Оценка приспособленности хромосом в популяции. В рассматриваемом упрощенном примере решается задача нахождения такой хромосомы, которая содержит наибольшее количество единиц. Поэтому функция приспособленности определяет количество единиц в хромосоме. Обозначим функцию приспособленности символом  . Тогда ее значения для каждой хромосомы из исходной популяции будут такие:    Хромосомы  и  характеризуются наибольшими значениями функции принадлежности. В этой популяции они считаются наилучшими кандидатами на решение задачи.Селекция хромосом. Селекция производится методом рулетки. На основании формул (1) и (2) для каждой из 8 хромосом текущей популяции (в нашем случае – исходной популяции, для которой  ) получаем секторы колеса рулетки, выраженные в процентах (рисунок 2).    Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому. Допустим, что разыграны следующие 8 чисел:  Это означает выбор хромосом  Как видно, хромосома была выбрана трижды, а хромосома – дважды. Заметим, что именно эти хромосомы имеют наибольшее значение функции приспособленности. Однако выбрана и хромосома  с наименьшим значением функции приспособленности. Все выбранные таки образом хромосомы включаются в так называемый родительский пул. Рисунок 2. Колесо рулетки для селекции. Применение генетических операторов. Допустим, что ни одна из отобранных в процессе селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Это означает, что вероятность скрещивания , а вероятность мутации  . Допустим, что из этих хромосом случайным образом сформированы пары родителей Для первой пары случайным образом выбрана точка скрещивания  , для второй  , для третьей  , для четвертой  . При этом процесс скрещивания потакает так как показано на рисунке 3. В результате выполнения оператора скрещивания получаются 4 пары потомков.Если бы при случайном подборе пар хромосом для скрещивания были объединены, например,  и  вместо  и  , а другие пары остались без изменения, то скрещивание дало бы две такие же хромосомы независимо от разыгранной точки скрещивания. Это означало бы получение двух потомков, идентичных своим родителям. Заметим, что такая ситуация наиболее вероятна для хромосом с наибольшим значением функции приспособленности, т.е. именно такие хромосомы получают наибольшие шансы на переход в новую популяцию. Рисунок 3. Процесс скрещивания хромосом Формирование новой популяции. После выполнения операции скрещивания мы получаем следующую популяцию потомков:     Для отличия от хромосом предыдущей популяции обозначения вновь сформированных хромосом начинаются с заглавной буквы С. Согласно блок-схеме генетического алгоритма (рисунок 1) производится возврат ко второму этапу, т.е. к оценке приспособленности хромосом их вновь сформированной популяции, которая становится текущей. Значения функций приспособленности хромосом этой популяции составляют     Заметно, что популяция потомков характеризуется гораздо более высоким средним значением функции приспособленности, чем популяция родителей. Обратим внимание, что в результате скрещивания получена хромосома  с наибольшим значением функции приспособленности, которым не обладала ни одна хромосома из родительской популяции. Однако могло произойти и обратное, поскольку после скрещивания на первой итерации хромосома, которая в родительской популяции характеризовалась наибольшим значением функции приспособленности, могла просто «потеряться». Помимо этого «средняя» приспособленность новой популяции все равно оказалась бы выше предыдущей, а хромосомы с большими значениями функции приспособленности имели бы шансы появиться в следующих поколениях [7]. 1 2 |
до L – из генов второго родителя;