WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 |

«Введение в генетические методы Автор: Конушин Антон ktosh Целый класс методов глобального поиска был построен по образу и подобию, данному нам самой Природой. ...»

-- [ Страница 1 ] --

Введение в генетические методы

Автор: Конушин Антон ktosh@zmail.ru

Целый класс методов глобального поиска был построен по образу и подобию, данному нам самой Природой. Природа

давно экспериментирует со своими игрушками - живыми существами, все время пытаясь найти наиболее

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

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

Вступление Постоянно в нашей жизни мы добиваемся самого лучшего. Ну, если не самого, то нам подходящего. Это касается всего, чтобы мы не делали, пишем ли мы программу, выбираем книгу и думаем об ужине.

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

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

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

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

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

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

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

Понятие оптимизации.

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

Примером задачи оптимизации может служить поиск минимума функции z = |x+sin(32*x)|. Областью поиска является все пространство вещественных чисел, целевым условием - минимум функции.

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

"Машинное обучение это наука, изучающая компьютерные алгоритмы, автоматически улучшающиеся во время работы".

Примером подобного рода алгоритмов являются нейросети.

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

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

Стратегия поиска Правила выбора для применения в данный момент того или иного оператора поиска называются стратегией поиска.

Существует множество стратегий поиска, в данном случае рассмотрим три главных:

• поиск вслепую (blind search) • подъем по холму (hill-climbing) • поиск по лучу (beam search) При поиске в слепую не учитываются ни результаты предыдущих шагов, ни какая-либо информация о задаче. Поиск происходит только в соответствии со структурой представления пространства поиска.

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

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

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

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

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

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

Если подходить к описанию эволюции более формально, то вначале необходимо отметить что объектом развития (т.е.

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

1. Каждый индивид в популяции способен к размножению 2. Отличия индивидов друг от друга влияют на вероятность их выживания 3. Каждый потомок наследует черты своего родителя (подобное происходит от подобного) 4. Ресурсы для поддержания жизнедеятельности и размножения ограничены, что порождает конкуренцию и борьбу Все процессы в живых организмах работают за счет сложных молекул - белков. Каждый белок представляет собой маленький биологический автомат. Молекула белка состоит из последовательности аминокислот. Совокупность информации и строении всех белков в организме определяет его изначальную структуру (развитие организма происходит также и под действием внешней среды). Вся эта информация называется генетической информацией, или генотипом. Процесс построения, развития организма по информации из генотипа называется онтогенезом. А строение, качества и свойства организма - фенотип. Т.к. внешняя среда воздействует на организм в целом, то можно сказать, что вероятность выживания организма определяется фенотипом.

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

Для кодирования информации используется 4 вида нуклеотидов, обозначаемых по названиям входящих в них азотистых оснований А,T,G,C. Таким образом алфавит кодировки состоит из 4 букв.. Последовательность из 3-х нуклеотидов называется кодон. Каждый кодон соответствует одной из аминокислот. Всего имеется 20 базовых аминокислот и кодона, а значит каждой аминокислоте соответствует более одного кодона, поэтому кодировка является избыточной.

Участки ДНК, несущие информацию о строении какого-нибудь белка клетки, назовем полезными сегментами. Полезные сегменты, описывающие некоторое свойства индивида (фенотипа), называются геном. А различные значения этого гена называются аллелями.

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

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

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



Pages:     || 2 | 3 | 4 |
 


Похожие работы:

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

«Ознакомился и согласен с настоящими условиями Toyota Extracare Имя, дата и подпись клиента 2012.04 / 4 издание ДОПОЛНИТЕЛЬНАЯ ГАРАНТИЯ TOYOTA EXTRACARE Уважаемый Клиент! Благодарим Вас за то, что Вы выбрали программу дополнительной гарантии Toyota Extracare. Выбирая дополнительную гарантию Toyota Extracare, Вы можете быть уверены в том, что Ваш автомобиль защищен гарантией производителя Toyota и после окончания срока действия оригинальной гарантии. Toyota Extracare обеспечит Вам спокойствие и...»

«Переведено на сайте www.notabenoid.com http://notabenoid.com/book/4063/ Переводчики: Injekcia, Anonimka, Timson, tipopellet, Dove_Dm, Sarnetsky, zombie_new, jyulya, Miss_Lia, remas, yuliasha, 1000and1, analyst, asdp555, bananapapa, BellaTe, CurlyWind, fustacre, GaponovAlex, Irina73, marvel, mipolina, Mirabella, REUn10n, someonelikethey, soroka, Stan, vadikgg, Viktorianka, Wetold. Оглавление Книга I 1 2 3 4 5 6 7 8 9 10 11 Книга II 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Книга III 28 29...»

«Счастливая беременность. Успешные роды. Настольная книга будущей мамы Ирина Солеева 2 Книга Ирина Солеева. Счастливая беременность. Успешные роды. Настольная книга будущей мамы скачана с jokibook.ru заходите, у нас всегда много свежих книг! 3 Книга Ирина Солеева. Счастливая беременность. Успешные роды. Настольная книга будущей мамы скачана с jokibook.ru заходите, у нас всегда много свежих книг! Ирина Александровна Солеева Счастливая беременность. Успешные роды. Настольная книга будущей мамы 4...»

«• К.Б.СВЕЧИН, И.Ф.БОБЫЛЕВ, БМ.ГОПКА КОНЕВОДСТВО Д о п ущ е н о Главны м уп р авлен и ем вы сш и х учеб ны х заведений М и н и стер ств а сел ьско го хо зяй ства Р о сси йско й Ф е д е р а ц и и в кач естве учеб н ика д л я студ ен то в се л ь с к о х о зя й с тв е н н ы х и н сти туто в по сп е ц и а л ь н о сти Зо о техн и я 2-е издание, переработанное и дополненное ф МОСКВА КОЛОС 1992 ББК 46.11 С 24 УДК 636.1(075.8) Редактор О. Ю. Калугина Рецензент А. А. Ремизов, заслуженный зоотехник РСФСР...»

«Отчет подготовлен для демонстрации методического подхода аналитического отдела компании Мониторинг социальных медиа (BrandSpotter.ru) к исследованиям, основанным на мнениях пользователей. Центральный бренд для анализа и два бренда в роли его конкурентов выбраны произвольно. Ни один из упомянутых брендов не связан с компанией Мониторинг социальных медиа, не является заказчиком данного отчета и не был поставлен в известность об исследовании. В отчетах использованы данные из открытых источников....»

«Стратегия Санкт-Петербург 2012 Серия книг Ликбез по управлению Часть 5 Школа классического правления Свага www.scgovern.org 2 Стратегия/ Сост. С.В.Короткий. – www.scgovern.org. Школа классического правления Свага, 2012 Короткий С.В., 2012 Серия книг Ликбез по управлению Часть 5 Школа классического правления Свага www.scgovern.org 3 Содержание Мир имеет два тела, одно – зримое, другое – незримое. Парацельс Задача правления Понятие стратегии Источник стратегии Тайна стратегии Определение...»

«Создай Свой СУПЕРЗАГОЛОВОК за 32 Секунды! 22 САМЫЕ МОЩНЫЕ И ПРОВЕРЕННЫЕ Схемы NLP для Создания КОММЕРЧЕСКИ ЭФФЕКТИВНЫХ ЗАГОЛОВКОВ! ВВЕДЕНИЕ. КОЛЛЕКЦИЯ АЛЬВИО Прием Первый: ПРЯМОЙ ИМПЕРАТИВ Прием Второй: ВОПРОСИТЕЛЬНЫЙ ЗАГОЛОВОК Прием Третий: ЗАГОЛОВОК- СВИДЕТЕЛЬСТВО Прием Четвертый: ПОЛУИМПЕРАТИВ Прием Пятый: НОУ-ХАУ Прием Шестой: КОСВЕННЫЙ ЗАГОЛОВОК Прием Седьмой: ЗАГОЛОВОК — ГАРАНТИЯ Прием Восьмой: ПРОБЛЕМА (ОГОРЧЕНИЕ) — РЕШЕНИЕ (НАДЕЖДА) Прием Девятый: ГАМБИТ Прием Десятый:...»

«ж Пер. с санскрита, предисловие и комментарий Андрея Игнатьева, Калининград, 2011 сшштдщт ТОшга двенадцатая Step, с санскрита, предисловие и крмментарий Андрея Игнатьева, Калининград, 2011 Предисловие Вашему вниманию представляется перевод с санскрита на русский язык двенадцатой книги Девибхагавата-пураны (в дальнейшем - ДБхП). Данное издание является продолжением моей многолетней работы по переводу этой известной пураны, начатой еще в 1999 году. Двенадцатая книга является одной из самых...»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.