ВВЕДЕНИЕ Искусственным интеллектом, или ИИ Artificial Intelligence – Аl, называют процесс создания машин, которые способны действовать таким образом, что будут восприниматься человеком как разумные. Это может быть повторение поведения человека или выполнение более простых задач, например, выживание в динамически меняющейся обстановке. Для некоторых исследователей результат данного процесса состоит в том, чтобы научиться лучше понимать
нас самих. Для других это база, на основе которой можно научить искусственные системы вести себя разумно. В любом случае ИИ обладает таким потенциалом для изменения мира, которого нет ни у одной другой технологии. В период становления ИИ его разработчики обещали достичь очень многого, но добились несравненно меньшего. В то время создание разумных систем казалось очень простой задачей, которая так и не была решена. В наше время цели создания ИИ стали намного практичнее.
ИИ был разделен на несколько частей, имеющих различные цели и средства их достижения. Проблема ИИ заключается в том, что технологии, которые исследуются в его рамках, становятся обычными сразу после их внедрения. Например, построение машины, которая смогла бы различать человеческую речь, когда-то считалось частью разработки ИИ. Теперь такие технологии, как нейронные сети и скрытые модели Маркова, уже никого не удивляют и не рассматриваются как разработка
ИИ. Родни Брукс описывает этот феномен как эффект ИИ. После того как технология ИИ находит применение, она перестает быть технологией ИИ, после своего создания эта технология перестает быть чудом и используется повсеместно. Так как искусственный интеллект по-разному понимается разными людьми, было принято решение использовать другую классификацию. Сильный ИИ представляет собой программное обеспечение, благодаря которому компьютеры смогут думать так же, как люди. Помимо возможности думать, компьютер обретет и сознание разумного существа. Слабый ИИ представляет собой широкий диапазон технологий ИИ. Эти функции могут добавляться в существующие системы и придавать им различные разумные свойства. В данной контрольной работе описаны некоторые технологии Слабого ИИ, которые по мнению автора контрольной работы являются интересными и актуальными, так как
объем контрольной работы не позволяет вместить все наиболее распространенные и известные алгоритмы и технологии ИИ. 1. Алгоритмы кластеризации Алгоритм кластеризации – это метод, благодаря которому данные разделяются и объединяются в небольшие группы кластеры по принципу аналогии. По тому же принципу осуществляется отделение несхожих данных, поэтому главной задачей при разбивке данных на кластеры является классификация. Хотя классификация используется во многих случаях, ее основное
предназначение – изучение данных в кластерах для выявления различий между ними. Более специфическое использование кластеров будет рассмотрено далее. 1.2 Биологическая мотивация Алгоритмы кластеризации имеют биологическое происхождение, поскольку предоставляют возможность обучения посредством классификации. Человеческий мозг изучает новые понятия, сравнивая их с уже существующими знаниями. Мы классифицируем новое, пытаясь объединить его в одном кластере с чем-
то, что нам уже известно это является основой для понимания нового. Если новое понятие нельзя связать с тем, что мы уже знаем, нам приходится создавать новую структуру, чтобы понять явление, которое выходит за рамки существующей структуры. Впоследствии эта новая модель может стать основой для усвоения другой информации. Объединяя новые понятия в кластеры с уже существующими знаниями, а также создавая новые кластеры для усвоения абсолютно новой информации мы решаем проблему, которую Гроссберг назвал дилеммой стабильности-гибкости. Вопрос состоит в том, как классифицировать новые данные и при этом не уничтожать уже изученные. Алгоритм АRТ1 включает все необходимые элементы, позволяющие не только создавать новые кластеры при обнаружении новой информации, но и реорганизовывать с ее учетом уже существующие кластеры. 1.3 Алгоритм АRТ1 Алгоритм
АRТ1 работает с объектами, которые называются векторами признаков. Вектор признаков является группой значений в двоичном коде, которые представляют определенный тип информации. Примером вектора признаков может служить выбор покупок. Каждый объект вектора признаков показывает, приобрел ли покупатель товар если да, то значение равно 1, если нет – 0. Покупатель купил молоток и гаечный ключ.
Этот вектор признаков описывает покупательную способность путем идентификации приобретенных покупателем предметов о которых мы имеем информацию. Собираются векторы признаков покупателя, к которым затем применяется алгоритм АRТ1, чтобы разделить данные на кластеры. Идея состоит в том, что группа схожих данных о покупателе содержащаяся в кластере будет сообщать интересную информацию о схожих параметрах для группы покупателей.
1.4 АRТ1 в деталях Мы начнем с группы векторов признаков назовем эти примеры Е1K и группы инициализированных векторов-прототипов Р1.N. Вектор-прототип является центром кластера. Количество векторов-прототипов, равное N. Является максимальным количеством кластеров, которое может поддерживаться. Параметр d показывает длину вектора. Мы инициализируем параметр внимательности р или rho, равный небольшому
значению между 0 и 1,0, а также бета-параметр В, равный небольшому положительному целому числу. Эти параметры будут рассмотрены более подробно. Vw побитовый И вектор v – Значимость v количество значимых элементов вектора N – Количество векторов-прототипов P Параметр внимательности 0 р 1 P Вектор-прототип E Вектор признаков d Размер векторовдлина B Бета-параметр Изначально не существует ни одного вектора-прототипа, поэтому при выполнении алгоритма создается первый вектор-прототип из первого вектора признаков Затем проверяются на схожесть все последующие векторы признаков с вектором-прототипом. Цель проверки выяснить, насколько схож вектор признаков и текущий вектор-прототип. Р0 Е0 1.1 Бета-параметр Р, который используется в уравнении проверки на схожесть уравнение 1.2 это
параметр разрушения связи. Он выбирает прототипы, в которых больше значений 1, при условии, что все значения 1 в векторе-прототипе также присутствуют в тестируемом векторе признаков. Pi E B Pi E B d 1.2 Если тест на схожесть прошел успешно, выполняется следующий тест, чтобы проверить вектор признаков и вектор-прототип против параметра внимательности уравнение 1.3. Задачей данного параметра является определение размера класса.
Если значение параметра велико, образуются более крупные классы кластеры с большим количеством данных. При уменьшении значения создаются кластеры с меньшим количеством данных. Если параметр внимательности задан Достаточно низким 0,1, для допуска векторы признаков должны соответствовать вектору-прототипу. Pi E E p 1.3 Наконец, если пройден тест на внимательность, алгоритм добавляет текущий вектор признаков в текущий вектор-прототип уравнение 1.4.
Этот процесс представляет собой простое слияние вектора признаков и вектора-прототипа c помощью операции И. Если тест на внимательность или тест на схожесть не был пройден , проверяется следующий вектор-прототип. Если все векторы прототипы были проверены и при этом вектор признаков не был помещен в кластер, создается новый вектор-прототип из вектора признаков. Это приводит к формированию нового кластера, так как рассматриваемый вектор признаков не соответствует ни одному существующему кластеру. Рi Рi Е 1.4 Теперь алгоритм проходит через все векторы признаков и сравнивает их со всеми векторами-прототипами. Создать начальный Выражение 1.1 Вектор-прототип Продолжить для Каждого вектора признаков Выражение 3.2 Выражение 3.3 похож ли вектор признаков да на вектор прототип нет нет проходит тест на внимательность Да да Еще прототипы нет Поместить вектор Признаков в текущий
Выражение 3.4 Вектор-прототип Хотя все векторы уже размещены по кластерам, проверка необходима. Она позволяет убедиться в том, что векторы расположены в нужных кластерах. Дело в том, чт0 последующие тесты векторов признаков могли создать новые кластеры, поэтом необходимо выполнить дополнительную проверку и удостовериться, что вектор Не нужно перемещать в другие кластеры. После проверки всех векторов признаков, которая не потребовала
дополнительных изменений, процесс формирования кластеров можно считать завершенным. Чтобы избежать перемещения вектора признаков между двумя векторами прототипами, алгоритм выполняет несколько итераций, чтобы объединит кластеры. Количество итераций должно быть достаточно большим, чтобы избежать преждевременного слияния. 1.5 Другие области применения Алгоритм АRТ1 предоставляет возможность классификации данных в отдельные сегменты кластеры.
Классификация может быть полезна как средство исследования классов типов кластеров. Кроме того, как видно по алгоритму персонализации, изучение членов отдельного кластера позволяет получить интересную информацию. Данный алгоритм можно использовать в следующих областях статистике распознавании образов уменьшении диапазона поиска биологии поиске в сети internet добыче данных . 1.6 Итоги В данной главе рассматривался простой алгоритм, который группирует данные в кластеры для системы выдачи рекомендаций. Изначально он создавался как инструмент, который может использоваться для обработки данных. Высокая эффективность алгоритма проявляется при обработке данных в сети internet в коммерческих целях. Пример алгоритма, представленный в этой главе, очень прост и работает с небольшим объемом данных. При персонализации в internet данные могут включать не только отображение содержания Web-страницы, но и время, которое было потрачено на ее просмотр.
Тип и отображение данных зависят от алгоритма, который выполняет персонализацию. При правильной кодировке в векторах признаков алгоритм АRТ1 может работать с широким диапазоном данных, отображающим многие аспекты поведения покупателя в сети internet. Несмотря на то, что существует и опасная сторона применения алгоритмов персонализации, они могут быть очень эффективными инструментами при сборе самой разнообразной информации.
2. Алгоритм муравья В этой главе рассматривается интересный алгоритм, основанный на применении нескольких агентов, с помощью которого можно решать самые разнообразные задачи. Алгоритмы муравья , или оптимизация по принципу муравьиной колонии это название было придумано изобретателем алгоритма, Марко Дориго , обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Природа предлагает различные методики для оптимизации некоторых
процессов. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статичных, но и динамических проблем, например, проблем маршрутизации в меняющихся сетях. 2.1 Естественная мотивация Хотя муравьи и слепы, они умеют перемещаться по сложной местности, находить пищу на большом расстоянии от муравейника и успешно возвращаться домой. Выделяя ферменты во время перемещения, муравьи изменяют окружающую среду, обеспечивают коммуникацию, а также отыскивают обратный путь в муравейник. Самое удивительное в данном процессе – это то, что муравьи умеют находить самый оптимальный путь между муравейником и внешними точками. Чем больше муравьев используют один и тот же путь, тем выше концентрация ферментов на этом пути. Чем ближе внешняя точка к муравейнику, тем больше раз к ней перемещались муравьи. Что касается более удаленной точки, то ее муравьи достигают реже, поэтому по дороге к ней они применяют
более сильные ферменты. Чем выше концентрация ферментов на пути, тем предпочтительнее он для муравьев по сравнению с другими доступными. Так муравьиная логика позволяет выбирать более короткий путь между конечными точками. Алгоритмы муравья интересны, поскольку отражают ряд специфических свойств, присущих самим муравьям. Муравьи легко вступают в сотрудничество и работают вместе для достижения общей цели. Алгоритмы муравья работают так же, как муравьи. Это выражается в том, что смоделированные муравьи совместно
решают проблему и помогают другим муравьям в дальнейшей оптимизации решения. Рассмотрим пример. Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного фермента, используя его в качестве маркера. При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает первый путь, а второй второй путь.
Так как второй путь в два раза короче первого, второй муравей достигнет цели за время Т1. Первый муравей в этот момент пройдет только половину пути. Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время Т2 второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи. Вспомните, что при перемещении каждого муравья на пути остается немного фермента. Для первого муравья за время Т0-Т2 путь был покрыт ферментом только один раз. В то же самое время второй муравей покрыл путь ферментом дважды. За время Т4 первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация фермента на втором пути будет в два раза выше, чем на первом. Поэтому первый муравей в следующий раз выберет второй путь, поскольку там концентрация фермента выше.
В этом и состоит базовая идея алгоритма муравья – оптимизация путем непрямой связи между автономными агентами. 2.2 Алгоритм муравья Подробно рассмотрим алгоритм муравья, чтобы понять, как он работает при Решении конкретной проблемы. Предположим, что окружающая среда для муравьев представляет собой закрытую двумерную сеть. Вспомните, что сеть – это группа узлов, соединенных посредством граней. Каждая грань имеет вес, который мы обозначим как расстояние между двумя узлами, соединенными ею.
Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении. 2 1 3 4 Граф с вершинами V 1,2,3,4 Грани Е 1,2,1,4,1,3,2,3,2.4,3.4 2.3 Муравей Муравей – это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список табу, то есть список узлов, которые он уже посетил.
Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона, по имени математика сэра Уильяма Гамильтона. Узлы в списке текущего путешествия располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой фермент. В алгоритме муравья агент оставляет фермент на гранях сети после завершения путешествия. 2.4 Начальная популяция После создания популяция муравьев поровну распределяется по узлам сети. Необходимо равное разделение муравьев между узлами, чтобы все узлы имели одинаковые шансы стать отправной точкой. Если все муравьи начнут движение из одной точки, это будет означать, что данная точка является
оптимальной для старта, а на самом деле мы этого не знаем. 2.5 Движение муравья Движение муравья основывается на одном и очень простом вероятностном уравнении. Если муравей еще не закончил путь, то есть не посетил все узлы сети, для определения следующей грани пути используется уравнение 2.1 Здесь – интенсивность фермента на грани между узлами r и u, -Функция, которая представляет измерение обратного расстояния для грани, a -вес фермента, а – коэффициент
эвристики. Параметры a и определяют относительную значимость двух параметров, а также их влияние на уравнение. Вспомните, что муравей путешествует только по узлам, которые еще не были посещены как указано списком табу. Поэтому вероятность рассчитывается только для граней, которые ведут к еще не посещенным узлам. Переменная k представляет грани, которые еще не были посещены. 2.6 Путешествие муравья Пройденный муравьем путь отображается, когда муравей посетит все узлы диаграммы.
Обратите внимание, что циклы запрещены, поскольку в алгоритм включен список табу. После завершения длина пути может быть подсчитана – она равна сумме всех граней, по которым путешествовал муравей. Уравнение показывает количество фермента, который был оставлен на каждой грани пути для муравья k. Переменная Q, является константой. 2.2 Результат уравнения является средством измерения пути короткий путь характеризуется высокой концентрацией фермента, а более длинный путь – более низкой. Затем полученный результат используется в уравнении 2.3, чтобы увеличить количество фермента вдоль каждой грани пройденного муравьем пути. 2.3 Обратите внимание, что данное уравнение применяется ко всему пути, при этом каждая грань помечается ферментом пропорционально длине пути. Поэтому следует дождаться, пока муравей закончит путешествие и только потом обновить уровни фермента, в противном случае истинная длина пути останется неизвестной.
Константа р – значение между 0 и 1. 2.7 Испарение фермента В начале пути у каждой грани есть шанс быть выбранной. Чтобы постепенно удалить грани, которые входят в худшие пути в сети, ко всем граням применяется процедура испарения фермента. Используя константу р из уравнения 2.3, мы получаем уравнение 2.4. 2.4 Поэтому для испарения фермента используется обратный коэффициент обновления пути.
2.8 Повторный запуск После того как путь муравья завершен, грани обновлены в соответствии с длиной пути и произошло испарение фермента на всех гранях, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разрешается перемещаться по сети, основывая выбор грани на уравнении 2.1 Этот процесс может выполняться для постоянного количества путей или до момента, когда на протяжении нескольких запусков не было отмечено повторных изменений.
Затем определяется лучший путь, который и является решением. 2.9 Области применения Алгоритм муравья может применяться для решения многих задач, таких как распределение ресурсов и работы. При решении задачи распределения ресурсов необходимо задать группу ресурсов n для ряда адресатов m и при этом минимизировать расходы на перераспределение то есть функция должна найти наилучший способ распределения ресурсов. Обнаружено, что алгоритм муравья дает решения такого же качества, как и другие, более стандартные способы. Намного сложнее проблема распределения работы. В этой задаче группа машин М и заданий J состоящих из последовательности действий, осуществляемых на машинах должны быть распределены таким образом, чтобы все задания выполнялись за минимальное время. Хотя решения, найденные с помощью алгоритма муравья, не являются оптимальными, применение алгоритма для данной проблемы показывает, что с его помощью можно решать аналогичные задачи.
Алгоритм муравья применяется для решения других задач, например, прокладки маршрутов для автомобилей, расчета цветов для графиков и маршрутизации в сетях. Более подробно способы использования алгоритма муравья описываются в книге Марко Дориго Алгоритмы муравья для абстрактной оптимизации 2.10 Итоги В этой главе описывался метод оптимизации поиска путей, позаимствованный у природы.
Алгоритм муравья моделирует поведение муравьев в их природной среде, чтобы определить оптимальный путь в пространстве по графу или сети. Данная технология рассматривалась как средство для решения задачи коммивояжера. ЗАКЛЮЧЕНИЕ Искусственный интеллект является классическим примером технологии, которая изначально казалась простой, но при более внимательном исследовании выяснилось, насколько она сложна. Ранние предсказания дальнейшей судьбы ИИ оказались ошибочными, что делает любые прогнозы будущего
ИИ, как минимум, недостоверными. Методы получения искусственного разума могут быть разделены на две категории ведение исследования сверху вниз и снизу вверх. Категория сверху вниз является синонимом традиционного подхода к ИИ, когда во главу угла ставилась задача создания ИИ и мало внимания придавалось деталям, позволяющим добиться этой цели. Категория снизу вверх схожа с моделью нейронной сети она почти полностью повторяет структуру человеческого мозга. С данной точки зрения познавательная способность разума зависит от работы огромного количества простых элементов. В этом подходе также используются эволюционные алгоритмы и искусственная жизнь. Представим человеческий мозг. Нам еще предстоит понять, какие структуры мозга отвечают за то, что мы называем разумом или сознанием. Процесс работы миллионов нейронов каким-то образом создает разум на глобальном уровне. Простой процесс действия нейрона на микро уровне способствует формированию гораздо
более сложного процесса на макро уровне. ИИ начинал свое развитие на уровне сверху вниз, причем разработки в области его связей были минимальны. После того как Марвин Мински и Сеймур Паперт опубликовали книгу Перцептроны, исследования в области нейронных сетей были почти полностью прекращены. Однако разработчики быстро поняли, что проблемы, описанные в данной книге, легко поддаются решению. Как считают сегодня, методика снизу вверх связана с будущим
ИИ. Главный вопрос в области ИИ формулируется так можем ли мы создать ИИ, который будет копировать человеческий разум, или мы опишем наши задачи и позволим ИИ на основе их решения обрести разум. Результаты изучения в этих сферах показывают, что нам следует руководствоваться методом снизу вверх. Алан Тьюринг первым предложил идею Машины-ребенка, принцип которой состоит в том, что разумная машина не станет разумной в одно мгновение,
а будет постепенно учиться, как это делают дети. Стремление к обучению будет запрограммировано, но знания машины будут улучшаться с течением времени. Другие исследователи предположили, что верный подход к проблеме – это изучение и построение искусственных животных. Сможем ли мы, к примеру, создать искусственное насекомое, которое сможет повторять поведение настоящего насекомого и учиться так же, как оно Эта задача, разумеется, намного проще, чем создание разума, подобного человеческому, но, очевидно, ее решение поможет нам при построении искусственного разума. Свое логическое развитие идея создания искусственных насекомых, живот-ных и людей нашла при построении роботов. Эта задача требует инноваций в сфере развития и проектирования микродатчиков и приводов, а также программных структур, способствующих неограниченному обучению системы. ИСПОЛЬЗУЕМАЯ ЛИТЕРАТУРА 1. Джонс М.Т. Программирование искусственного интеллекта в приложениях
Пер. с англ. Осипов А.И Москва 2004 2. Журнал Мир ПК 3 2002.