Лекции по ПСУ, ч.2. Лекция 1 Критериальный язык описания задачи выбора

• Название: Лекция 1 Критериальный язык описания задачи выбора
• Дата: 14.03.2023
• Размер: 4.27 Mb.
• Имя файла: Лекции по ПСУ, ч.2.doc
• Тип: Лекция; #988620
• страница: 4 из 5

6.4.3. Генетический метод комбинирования эвристик
Пусть N – число работ, М – число серверов. Если гены соответствуют номерам работ, то в первом подходе в хромосоме нужно иметь 2N генов и общее число отличающихся друг от друга хромосом W заметно превышает наибольшее из чисел N! и М ^N.

W> N! W> М ^N

Согласно методу комбинирования эвристик, число генов в хромосоме в два раза меньше, чем в первом подходе, и равно N. Поэтому если число используемых эвристик равно К, то мощность множества возможных хромосом уже несравнимо меньше, а именно
W=K^N.
Лекция №6

6.5. Эволюция сложных систем
6.5.1. Использование знаний о ЕС в ИС
Идеи применения знаний о живой природе для решения задач в ИС принадлежат еще Леонардо да Винчи, который спроектировал и пытался построить летательный аппарат с движущимися крыльями как у птиц. Наблюдения из области адаптации живых организмов приводили, приводят, и будут приводить к идеям, позволяющим наделить подобными свойствами автоматические и автоматизированные системы искусственного происхождения.

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

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

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

В 1953 г. с работ М. Уоткена и Ф. Крика началась новая наука – молекулярная генетика. Биохимические особенности живых организмов наследуются по законам, которые открыл Г. Мендель. В генах «записаны» планы строения белков – планы всех наследственных признаков. Генетический код оказался общим для всех естественных систем на нашей планете. Он практически расшифрован. Каждая хромосома уникальна морфологически и генетически и не может быть заменена другой либо восстановлена при утере. При потере хромосомы клетка, как правило, погибает. Каждый биологический вид имеет определенное, постоянное число хромосом.

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

1) все признаки организмов находятся под контролем генов;

2) гены – элементарные единицы наследственной информации, они находятся в хромосомах;

3) гены могут изменяться – мутировать;

4) мутации отдельных генов приводят к изменению отдельных элементарных признаков, или фенов.

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


Чарльз Дарвин
Ч. Дарвин по существу впервые дал строго научную теорию эволюции. Она состоит из следующих положений:

1) В ЕС все подвержено неопределенной наследственной изменчивости, потомство производится, отличающееся по многим признакам. В настоящее время считается, что изменчивость – результат мутаций, т. е. изменения в строении генов ДНК.

2) Все организмы в ЕС размножаются таким образом, что число появляющегося на свет потомства превосходит число взрослых особей, но численность всех организмов в среднем остается более или менее постоянной, она колеблется около средней величины.

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


Рис. 26. Схема эволюции Ч.Дарвина
Согласно теории Ч. Дарвина, эволюция осуществляется во взаимодействии трех повторяющихся вновь процессов: отбора, амплификации, мутации. Амплификация – процесс производства потомков или более точно, копирование особей, действует в природе совместно с отбором. Критерий отбора подобен библейскому: «плодитесь и размножайтесь». Стратегия повторяющейся рандомизации может заставить молекулы эволюционировать в направлении улучшения функциональных характеристик.
6.5.5. Ламаркизм
Первая группа концепций и гипотез учения об эволюции связывается с именем Ж. Ламарка. В 1809 г. он предположил, что все живые организмы целесообразно приспосабливаются к условиям среды. Ж. Ламарк предложил свою концепцию эволюции до теории эволюции Ч. Дарвина о естественном отборе. Его теория основана на предположении, что характеристики, приобретенные организмом в течение жизни, наследуются потомками. Он предложил ее как средство, при помощи которого организм передает специальные черты для выживания в среде, и это положение известно как теория эволюции Ж. Ламарка или ламаркизм.



Жан Батист Ламарк (1744 – 1829)
Причинами эволюции Ж. Ламарк считал стремление всех живых организмов к прогрессу, развитию от простого к сложному (учение о градации (уровень, ступень)), а также целесообразные изменения организмов, направленные на приспособление к внешним условиям. Эти изменения, как утверждал Ж. Ламарк, вызываются прямым влиянием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков. Его считают основоположником телеологической (греч. teleos – результат, цель и logos – наука) теории эволюции, согласно которой способность организмов приспособляться к окружающей среде есть врожденное свойство жизни.

Ж. Ламарк объясняет одну из особенностей эволюции органического мира приспособляемостью. Прогрессивную эволюцию, появление форм, более сложных и совершенных, он объяснял «законом градаций» – стремлением живых существ усложнять свою структуру. Приспособительные изменения, возникнув один раз, далее, по мнению Ж. Ламарка, способны передаваться по наследству (концепция «наследования благоприобретенных признаков»). Его концепция не дает четкого объяснения эволюции. Согласно ей виды эволюционируют, приспособляясь и усложняясь, потому что у них существуют свойства – приспособляться и усложняться. Причины направленных изменений объясняются различно, но их можно свести к двум:

1) направленное влияние внешней среды; 2) способность самого организма.

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



Аристотель (384 – 322 г. до н.э.)
Так и в эволюции по Ж. Ламарку – большая приспособленность потомков возникает в результате целенаправленной изменчивости предков. Согласно ламаркизму предполагается, что живые организмы способны сами находить верное решение, как себя улучшить, и, более того, сами же способны свое решение осуществлять. Зная, как сложно устроена ЕС, легко понять, что это затруднительно. Ламаркизм не объясняет большинство эволюционных преобразований.

Ж. Ламарк попытался создать целостную эволюционную теорию. Согласно ей, переход от низших форм жизни к высшим – градация. Она происходит в результате имманентного и всеобщего стремления ЕС к совершенству. Ламаркизм эволюцию объясняет адаптацией. Разнообразие видов на каждом уровне организации объясняется модифицирующим градацию воздействием условий среды. Ж. Ламарком выведены два закона:

1. Упражнение органов приводит к их прогрессивному развитию. Неупражнение органов приводит к редукции.

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

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

Эволюция Ж. Ламарка является мощной концепцией искусственной эволюции, применимой в науке и технике, несмотря на то, что она дискредитирована в биологии. Авторы предлагают использовать некоторые принципы этого типа эволюции для построения интеллектуальных ИС и решения оптимизационных задач.

Мутационный процесс, обладая собственными закономерностями, поставляет сырой материал для эволюционного процесса в виде новых, мутационно возникающих генов. Эти гены вступают в состав генофонда вида, который сохраняет их вне зависимости от их эволюционного значения в пределах, дозволяемых естественным отбором. Согласно закону Гарди (равновесие популяции) и закону Пирсона (стабилизирующее скрещивание), если на популяцию не действуют внешние факторы, то закономерности популяции поддерживают наследственное строение в неизменном состоянии. На рис. 27 приведена одна из возможных схем механизма эволюционного процесса.

Рис. 27. Механизм эволюционного процесса по Ж.Ламарку

6.5.6. Сальтационизм
Ян Лотси, У. Бетси, де Фриз, В. Гольдшмидт, В. Кордюм в своих работах отклоняли интегрирующую роль естественного отбора, а в процессах появления мутаций видели непосредственно факторы видообразования. Они и развили идеи сальтационизма, по которым основным путем происхождения видов служат внезапные скачки без предварительного накопления количественных изменений в процессах эволюции. Такой механизм эволюции иногда называют эволюцией катастроф. Он проявляется ориентировочно один раз в нескольких тысячах поколений. Основная идея его состоит во внесении глобальных изменений в генофонд на момент катастрофы. Будем называть такую эволюцию – эволюцией де Фриза.


Хуго де Фриз (1848 – 1935)
Появление видов путем внезапных скачков – это реальный процесс.

Внешняя среда в конечном итоге определяет эволюцию, но не в простой форме связи между наследственной изменчивостью организмов и средой как в эволюции Ж. Ламарка, а в более сложной форме. Согласно Н. Дубинину модернизированная схема механизма эволюционного процесса с учетом эволюции де Фриза имеет вид (рис. 28).


Рис. 28. Модернизированный механизм эволюции Ж.Ламарка

с учетом эволюции де Фриза

6.5.7. Синтетическая теория эволюции
Эволюция Дарвина на основе естественного отбора на каждой из своих ступеней создает все новые условия генотипической среды. Естественный отбор закрепляет только те генотипы, которые дают приспособленный соответствующий данной внешней среде фенотип. Отбор – это, по форме, селектирующий фактор, а, по существу, – творческий процесс создания ЕС или ИС. Дарвин говорил лишь о категории неопределенной изменчивости. В настоящее время ее подразделяют на мутационную и комбинационную, или комбинативную. С момента разделения изменчивости на две категории возникают предпосылки для создания новой, синтетической, теории эволюции. Она является синтезом дарвинизма, классической генетики и теории популяций. Суть ее в следующем: вновь образующиеся изменения генов, а также появляющиеся при этом в результате скрещивания комбинации генов подвергаются отбору под воздействием факторов внешней среды. Синтетическая теория эволюции объединила признанные положения эволюций Ч. Дарвина, Ж. Ламарка, Х. де Фриза и учение о генетике популяций. Основные положения синтетической теории эволюции согласно Н. Дубинину следующие:

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

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

3) в популяциях наследственная изменчивость имеет массовый характер. Появление специальных мутаций свойственно лишь отдельным особям;

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

5) специальные виды эволюций идут путем фиксации нейтральных мутаций на основе стохастического процесса;

6) реальным полем эволюции являются интегрированные генетические системы. Только при наличии разрывов между видовыми генетическими системами могла возникнуть и развиваться эволюция;

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

8) самодвижение представляет собой внутреннее необходимое самопроизвольное изменение системы, определяемое ее противоречиями;

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

Полная модифицированная схема синтетической теории эволюции показана на рис. 29.

Рис. 29. Полная схема механизма эволюционного процесса

6.5.8. Обобщенная эволюция К.Поппера


Карл Раймунд Поппер (1902 – 1994)
Она излагается в виде 12 тезисов, основными из которых являются следующие:

1) все ИС и ЕС решают проблемы;

2) проблемы всегда решаются методом проб и ошибок;

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

4) популяция использует тот механизм управления, который выработался в процессе эволюции ее вида;

5) популяция представляет собой «головной отряд» эволюционного вида, к которому она принадлежит. Она сама является пробным решением, анализируемым в процессе эволюции, выбирающим окружающую среду и преобразующим ее;

6) эволюционная последовательность событий представляется в виде схемы

F₁ → TS → ЕЕ → F₂,

где F₁ – исходная проблема, TS – пробные решения, ЕЕ – устранение ошибок, F₂ – новая проблема.
В отличие от эволюции Ч. Дарвина, где существует одна проблема – выживания сильнейших, в эволюции К. Поппера существуют и другие проблемы: воспроизводство, избавление от лишнего потомства и т.д. Здесь большое значение имеет отличие F₁ от F₂, что как-то объясняет интеллектуальную творческую эволюцию.

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

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

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

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