Майлингова О.Л., Манжелей С.Г., Соловская Л.Б. - Прототипирование программ на языке Scheme (1108536), страница 10
Текст из файла (страница 10)
Можно описать модель, в которойконтекст (окружение) является той областью, в которой хранится значение.Оператор присваивания(set! variable expression)В результате выполнения процедуры set! вычисляется значениевыражения <expression>. Значение переменной <variabie> (котораядолжна быть уже определена с помощью define) становится равнымзначению выражения <expression>. При этом значение самого выраженияset! не определено.(define x 2}(+ х 1)(set! х 4)(+ х 1)->->->->не определено3не определено5Рассмотрим процедуру вычисления факториала числа.
Ее можно записатьв императивном стиле:(define (factorial n)(let ((product 1) (counter 1)(define (iter)(if (> counter n) product(begin (set! product (* counterproduct))(set! counter (+ counter 1)) (iter)))) (iter)))При этом порядок записи операторов присваивания играет существеннуюроль.Изменение структуры данныхСуществуют функции с побочным эффектом, изменяющие внутреннююструктуру данных.(set-car! <pair> <obj>)Метапеременная <pair> должна иметь тип пара. Происходитпереопределение пары, первым элементом которой становится указательна <obj >.
Значение выражения set-car! не определено.(set-cdr! <pair> <obj>)Метапеременная <pair> должна иметь тип пара. Происходитпереопределение пары, вторым элементом которой становится указательна <obj >. Значение выражения set-cdr! не определено.Последовательность выраженийЕсли синтаксис языка требует наличие ровно одного выражения, как,например в if выражении, можно воспользоваться объединяющимивыражениями sequence и begin.(sequence expressionl expression2 .
. . )(begin expressionl expression2 ...)При вычислении этих выражений происходит последовательное (слеванаправо) вычисление подвыражений. Результатом является значениепоследнего подвыражения.(begin (set! х 5) (+ х 1) )-> 6(sequence (print "4 plus 1 equals ")(print ( + 4 1 ) ) )-> не определено55В последнем случае будет напечатано «4 plus 1 equals 5». А значениевсего выражения не определено, так как значение последнего выраженияprint также не определено.56Глава 3Решение задач и механизмы эволюцииТрадиционные способы решения задач основаны либо надетерминированных моделях (существует четкий алгоритм вычислениянеизвестных параметров по исходным данным, например, теоремаПифагора), либо на вероятностных моделях, применяемых в сочетании состатистическим подходом (исходные данные получаются по выборкамнаблюдаемых значений).
При работе с такими моделями используютсяхорошо известные математические методы: методы линейногопрограммирования, градиентные методы, полный перебор.Использование детерминированных моделей несомненно является«наилучшим» способом: используется найденная и доказанная формула,которая во всех случаях дает решение поставленной задачи. Но, ксожалению, подходящие формулы существуют далеко не для всех задач.Тогда на помощь приходят методы перебора, традиционно используемыепри решении широкого класса задач, имеющих комбинаторную природу.Сущность любой комбинаторной задачи можно сформулироватьследующим образом:«Найти на множестве X элемент х, удовлетворяющий совокупностиусловий К(х), в предположении, что пространство поиска X содержитнекоторое конечное число различных точек».Если требуется найти элемент, принадлежащий некоторому конечномумножеству, можно перебирать все элементы, пока не найдетсяподходящий.
Этот метод прост, надежен и хорошо работает, еслимощность множества невелика. Такой метод полного перебора можноусовершенствовать, вместо рассмотрения всего элемента У. можноограничиться некоторым его фрагментом, достаточным для проверкивыполнения (невыполнения) условия К(х). При этом наиболееблагоприятным является случай, когда можно определить градиент.Суть градиентного метода состоит в том, что для скорейшего достижениявершины надо продвигаться по самому крутому склону.
Каждойконкретной точке поискового пространства ставится в соответствиенекоторая числовая оценка, достигающая экстремума в целевой вершине, ина каждом шаге выбирается действие, которое дает максимальноеприращение оценочной функции. К градиентным методам относятсясимплекс-метод в линейном программировании, А*-процедура, методы57последовательных приближений в численном анализе, минимаксныеметоды, метод ветвей и границ, динамическое программирование [8].Но для многих практических задач (например, прогнозирование курсавалют, оптимальное распределение инвестиций) применениетрадиционных методов решения связано с рядом трудностей.
В частности,исходных данных может быть недостаточно для описания полной модели,алгоритм решения задачи может быть вовсе неизвестен, а использованиематематических методов решения может привести к неприемлемымзатратам вычислительных ресурсов и времени.
Также стоит отметить, чтоматематические методы решения накладывают существенные ограниченияна рассматриваемые модели. Например, симплекс-метод применим толькок линейным функциям, а градиентные методы в чистом виде не пригодныдля задач глобальной оптимизации, статистические же методы хорошоразвиты только для одномерных случайных величин, а вычислениемногомерных статистических моделей зачастую требует использованияэвристических подходов.Поэтому среди современных аналитических технологий определеннуюпопулярность приобретают методы, имитирующие процессы развитияприроды (рассматриваемые ранее только в теории искусственногоинтеллекта). В частности, принципы работы человеческого мозгапослужили основой для создания теории нейронных сетей. А процессы,описанные Ч.
Дарвином в его теории эволюции, легли в основу такназываемых генетических алгоритмов. Нейронные сети, генетическиеалгоритмы и их комбинации являются наиболее изученными ипроработанными методами из этого семейства аналитических технологий.Эксперименты показали, что механизмы генетической эволюции успешноиспользуются при решении задач, для которых не существует четкихалгоритмов и пространство возможных решений велико. Например, задачиоптимизации, прогнозирования, классификации, разного родакомбинаторные задачи.
По шкале сложности, принятой в теорииалгоритмов, такие задачи, как правило, относятся к классу NP-полныхзадач. На практике, эти методы применяются для эвристическогосокращения полного перебора в экспертных системах, распознаванияобразов, прогнозирования доходов, составления оптимальных маршрутов,расписаний, проектирования и оптимизации сетей связей и т.д.Генетические алгоритмыГенетический алгоритм (ГА) представляет собой метод поискаоптимальных решений, основанный на имитации эволюционных58процессов развития популяции хромосом (смена поколений, естественныйотбор, наследование, мутация).Основные понятия генетического алгоритма:1.
Ген - элементарная единица информации (например, 0 и 1).2. Хромосома - последовательностьгенов(например,битоваяпоследовательность из 0 и 1), кодирующая некоторую полезнуюинформацию.3 Популяция - множество хромосом, которое обрабатывается с помощьюалгоритмов репродукции, изменчивости, генетической композиции.Наиболее важные среди них - скрещивание генетического материала,содержащегося в родительских хромосомах и случайные мутацииданных в индивидуальных хромосомах.4. Скрещивание - в популяции случайным образом выбираются двехромосомы-родители; произвольный номер гена разбивает каждуюхромосому на две части; два потомка получаются в результате обменасоответствующими составными частями хромосом-родителей; размерхромосом при этом не изменяется.5. Мутация - в популяции случайным образом выбирается однахромосома; в ней выбирается некоторый ген, значение которогозаменяется произвольным из области допустимых значений.6.
Пригодность хромосомы - неотрицательное число, определяющеестепень пригодности хромосомы для решения задачи.7. Оценочная функция - функция одного аргумента, которая для каждойхромосомы возвращает значение ее пригодности.8. Естественный отбор-выбор «лучших» хромосом для участия вдальнейшей репродукции популяции.Для решения задачи с помощью ГА сначала строится исходная популяция,представляющая собой множество возможных решений, полученныхпроизвольным образом и закодированных в виде хромосом.
Как правило,задачи, решаемые ГА, имеют большое пространство возможных решений.Начальная популяция состоит из некоторого их подмножества. Например,для поиска экстремума функции на отрезке, в качестве исходнойпопуляции можно взять все числа из этого отрезка, расположенные нарасстоянии некоторого фиксированного интервала друг от друга, илипросто случайные числа из этого отрезка.Главная проблема построения алгоритмов генетической эволюции - этокодирование информации. В клетке любого живого организма хромосомапредставляет собой молекулу ДНК (Дезоксирибонуклеиновая Кислота).Одна молекула ДНК - это цепочка, состоящая из нуклеотидов четырехтипов (А, Т, С и G), представляющих минимальную единицу генетическойинформации. В программировании традиционно элементарной единицей59информации является бит.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
