Диссертация (IT-центризм антропологическая периферийность информационного общества), страница 9

Плоскость разбита на 16равных квадратных клеток, на 15 из них размещаются пронумерованныепредметы от 1 и до 15, одна клетка – одно число. Клетки считаются соседними,55Галимова А.М. Эволюция понятия алгоритм и его разделение по видамвычислимости//Международная летняя школа-семинар по искусственному интеллекту длястудентов, аспирантов и молодых ученых. ISyT`2011.

Тверь-Протасово. 2011.56Трахтенборт Б.А. Алгоритмы и машинное решение задач. М., 1957. С. 12-23.45если границы входят в один общий отрезок; смежными называются те позиции,которые позволяют видоизменить свое положение по результатам хода,использую пустую клетку. Комбинация самих позиций конечна и равна 16! = 20922 789 888 000, и при этом с каждой позиции можно сделать толькоограниченное количество ходов – от двух до четырех.Задача заключается в решении следующего вопроса: нужно для двухлюбых позиций выяснить, возможно ли перевести одну [позицию] в другуюконечной последовательностью шагов.

При утвердительном ответе возникаетцепочка эквивалентных ходов, ведущих от начального пункта к исходномурезультату, при этом позиции не должны повторяться. Число самих ходов привыполнении всех условий – не более 16! – 1. Затем строится разрешающийалгоритм с перебором всех возможных комбинаций из от 1 до 16! – 1 ход. Списоквыглядит как перебор смежных позиций, потом смежных с этими смежными, итак далее 16! – 1 раз. Когда в этом списке возникает искомая ситуация, то мысчитаем ответ утвердительным, если нет, то отрицательным.Одним из важнейших свойств алгоритма является его универсальность, тоесть принципиальная возможность допускать описание любых алгоритмовразличнымисредствами.универсальныхЗдесьалгоритмическихможновыделитьмоделей,триосновныхразличающихсятипаисходнымиэвристическими соображениями относительно того, что такое алгоритм.Первый тип связывает понятие алгоритма с наиболее традиционнымипонятиями математики, а именно, вычислениями и числовыми функциями.Наиболее развитая и изученная модель этого типа – рекурсивные функции (Черч),она является исторически первой строгой формализацией понятия алгоритма.Второй тип модели уже связан с развитием вычислительной техники иоснован на представлении об алгоритме как о некотором детерминированномустройстве, способном выполнять в каждый отдельный дискретный моментвремени весьма примитивные операции.

Основной теоретической моделью этого46типа является реализованная идея машины Тьюринга57. Именно машинаТьюринга стала моделью современной электронно-вычислительной машины испособствовала развитию современной вычислительной техники.Третий тип алгоритмических моделей – это преобразование слов впроизвольных алфавитах, в которых элементарными операциями являютсяподстановки, то есть замены части слова или «подслова» другим словом.Преимущества этого типа моделей заключаются в максимальной абстрактности ивозможности применить понятие алгоритма к объектам произвольной, необязательно числовой природы.

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

Вэтом ракурсе алгоритмы можно представить в виде дискретных, аналоговых игибридных вычислений. Дискретные [алгоритмы] предназначены для работы сдискретными, численными или символьными переменными. Переход междудискретными состояниями «вкл/выкл», {0/1} при аналоговых вычисленияхосуществляется с помощью непрерывного изменения того или иного физическогопараметра. Гибридные сочетают в себе оба вида вычислений.Дискретные алгоритмы.

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

Именно так и появились эволюционные или генетические алгоритмы.57Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений =Introduction to Automata Theory, Languages, and Computation. М.: «Вильямс». 2002. 528 с.47Вычислительная техника испытала на себе не только искусственно созданныемодели, но и модели, форму которых нам подсказывает жизнь. Для решения задачпооптимизации,основываясьнаоткрытияхвобластибиологическойнаследственности, Джон Холланд в 1975 году решил создать базовый алгоритм вэволюционныхвычислениях.Вчестьсоздателяонполучилназвание«репродуктивного плана Холланда», и очень широко использовался на практике.Эту идею стали развивать и дальше, упоминания этого термина – генетическиеалгоритмы - появились уже в работах Гольдберга и Де Йонга.58Описание генетического алгоритма выглядит достаточно просто, но самивычисления требуют специализированной подготовки.

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

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

Если задуматься, то их«бытовой уклад» устроен максимально рациональным образом. Казалось бы, гдекомпьютер с его алгоритмами и языками программирования, а где - насекомые,какая между ними может быть связь?! Для лучшего понимания себя человек частоприбегает к опыту, который нам демонстрирует природа, и научная деятельность58Макконел Д. Основы современных алгоритмов. М., 2004. С. 356-361.48- не исключение. Остановимся на муравьиных алгоритмах, где Марк Дориго всвоем диссертационном исследовании в 1992 году предложил взглянуть на этотприродный механизм под другим, не-биологическим углом и, учитываяполученные феноменальные данные, решать задачи по оптимизации.

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

Привыборе узла, муравей всегда помнит об уже пройденных им путях и, воссоздаваяих в качестве запретных, больше ими не пользуется, что на языке алгоритмовзначит – не переходит к следующему шагу. «Tabu list» является бесконечнопополняемым новыми узлами, а каждый новый шаг алгоритма при возобновлениипохода по тому же пути, он опустошается.Муравьи пользуются не только списками запретов, но и особойпривлекательностьюсамихпутей.Привлекательностьвыстраиваетсявзависимости от расстояния между соседними узлами, а также от следовферомонов, оставленных муравьями из той же колонии. Если степень оценки«качества» узла остается константной, то каждая итерация алгоритма по следамферомонов обновляется, так как они могут усиливаться или наоборот испаряться.Для большей наглядности представлен пример.59Штовба С.Д.

Муравьиные алгоритмы // ExponendaPro Математика в приложениях. 2003. № 4.С. 70-75.49На рисунке 1 два муравья начинают свой путь разными путями к «пище»через «препятствие» и находятся в равном положении. Но можно заметить, чтодля одного из них путь будет короче, чем для другого.РиРисунок 1На рисунке 2, пока первый муравей (верхний) прошел только половинупути, второй уже добрался до цели.Рисунок 250Рисунок 3:первый добирается до цели, второй уже успел вернуться сдобытым обратно в колонию.Рисунок 3Смоментауспешноговыполнениязадачиначинаетдействовать«муравьиный алгоритм» – концентрация феромонов второго муравья будетнамного выше, чем [концентрация феромонов] первого, и, когда в муравейниквернется первый, выбравший длинный путь, следующийон уже пойдет попроверенному пути.

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

Джеймс Уотсон и Френсис Крик совершилиоткрытие двойной спирали ДНК, а это послужило толчком для развития генетикикак отдельной отрасли научных исследований. Кроме того, открытие позволилоприменять на них особые алгоритмы, для которых переход на следующий шагявляется не таким «ступенчатым», а скорее похожим на непрерывный процесс. Овозможности построения квантовых компьютеров, и, соответственно, алгоритмов51к ним, впервые высказался Р.Ф. Фейнман, а в 1994 г.