Pull to refresh
  • by relevance
  • by date
  • by rating

Норвежцы создали компьютер, который умеет мутировать

Cyberpunk
Инженеры из университета Осло создали эволюционный компьютер, который меняет свою конфигурацию с помощью генетических алгоритмов. Как и животным в настоящем мире, компьютеру требуется 20–30 тысяч поколений и мутаций, чтобы адаптировать дизайн к решению новой проблемы. Однако здесь процесс занимает не миллионы лет, а всего несколько секунд.

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

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

via Bits of News
Total votes 61: ↑53 and ↓8 +45
Views916
Comments 60

Составление расписания ВУЗа

Lumber room
Привет всем, кто сталкивался с более или менее приемлимыми алгоритмами составления расписания в ВУЗе? Буду признателен за любую информацию по теме.
Total votes 23: ↑10 and ↓13 -3
Views1.7K
Comments 31

Генетические алгоритмы

Lumber room
Поставлена задача для оптимизации функций (поиск экстремумов). Выбрал генетические алгоритмы, как один из методов случайного направленного поиска. Что-то реализовал. Хотел бы поделиться и предлагаю присоединиться. В качестве примера взята простая функция и только целочисленные значения аргумента. Нужно развитие алгоритма для использования при оптимизации более сложных функций.
Total votes 5: ↑2 and ↓3 -1
Views808
Comments 8

Проблемы разработки реально быстрого ПО в наше время

Lumber room
Дрова пилятся, пилы совершенствуются, доски всё длинные и длинные,
а вот скорость наших программ не сопоставляется с размером этих досок…
Как-то задумал я раз в свои 18 писать компилятор большой-широкий, идей для него выписал целый блокнот.
Так и умер он за вечной оптимизацией собственного кода… =)

Я решил представить общественности несколько своих идей
и если что-то их заинтересовало прошу связаться со мной для определения подальшей деятельности.
Проще говоря — я искаю друзей, для разработки само-оптимизирующегося компилятора основаного на датамайнинге и генетических алгоритмах + много весёлых вкусностей стандартной библиотеки.

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

Ну начнём…
Читать дальше →
Total votes 39: ↑15 and ↓24 -9
Views462
Comments 25

Обзор методов эволюции нейронных сетей

Artificial Intelligence


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

Построение искусственной нейронной сети по традиционной методике выполняется, фактически, методом проб и ошибок. Исследователь задает количество слоев, нейронов, а также структуру связей между ними (наличие/отсутствие рекуррентных связей), а затем смотрит, что же у него получилось — сеть обучается с помощью какого-либо метода, а затем тестируется на тестовой выборке. Если полученные результаты работы удовлетворяют заданным критериям, то задача построения ИНС считается выполненной успешно; в противном случае — процесс повторяется с другими значениями исходных параметров.

Естественно, бурное развитие теории и практики использования генетических алгоритмов, заставило исследователей (лень — двигатель прогресса) искать способы применить их к задаче поиска оптимальной структуры ИНС (эволюция нейронных сетей или нейроэволюция), тем более, что, так сказать, proof-of-concept был налицо, или, точнее, в голове — природа наглядно демонстрировала решаемость подобной задачи на примере эволюции нервной системы с последующим образованием и развитием головного мозга.

Обзор и сравнение методов нейроэволюции под катом
Total votes 65: ↑60 and ↓5 +55
Views28.6K
Comments 32

«Hello world!» с помощью генетических алгоритмов

Algorithms
В наше время все большую популярность набирают генетические алгоритмы. Их используют для решения самых разнообразных задач. Где-то они работают эффективнее других, где-то программист просто решил выпендриться…

Так что же такое генетический алгоритм? Если верить википедии, то генетический алгоритм — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе.

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

Как это все выглядит вы можете увидеть на следующем рисунке:



Читать дальше →
Total votes 121: ↑108 and ↓13 +95
Views23.3K
Comments 60

Концепции практического использования генетических алгоритмов

Algorithms
Sandbox

Предисловие


На написание статьи вдохновили две публикации:

Захотел изложить свои мысли и свой взгляд на этот вопрос именно как практик от программирования «с математическим бэкграундом». Это будет повествование «на пальцах». Специалистом в генной инженерии не являюсь и сужу по поверхностным описаниям механизмов функционирования живых клеток и ДНК.
Читать дальше →
Total votes 34: ↑30 and ↓4 +26
Views9.3K
Comments 16

ТАУ-Дарвинизм

Algorithms

Предисловие


— Кибердворник дядя Федя силой ровно в три медведя, — сообщил Поль, извлекая из недр кибердворника блок регулировки. — Я тут уже знаю одного Федю. Приятный такой, веснушчатый. Очень, очень асептический молодой человек. Это не твой родственник?

Аркадий и Борис Стругацкие (Полдень. ХХII век).

Статья посвящена вопросу применимости генетических алгоритмов к проблеме идентификации динамической системы.
Обновлено: опубликовано продолжение ТАУ-Дарвинизм: реализация на Ruby
Как заглянуть в черный ящик читайте тут
Total votes 56: ↑50 and ↓6 +44
Views4.5K
Comments 41

ТАУ-Дарвинизм: реализация на Ruby

Ruby

Предисловие


Послушайте, ворона, а может быть собака,
А может быть корова, но тоже хорошо!
У вас такие перья, у вас рога такие,
Копыта очень стройные и добрая душа.

Мультфильм «Пластилиновая ворона».

В этой статье представляю Вашему вниманию реализацию эволюционного подхода к идентификации динамической системы. Программа написана на языке Ruby версии 1.9.2 (gems: NArray, GNUPlot). Заглянув под кат найдете пример вещественного кодирования генной информации и подходящего для него алгоритма скрещивания («flat crossover»).
Как узнать, кто есть кто, читать тут
Total votes 29: ↑21 and ↓8 +13
Views3.2K
Comments 8

Увеличение поисковых способностей генетических алгоритмов с помощью прогнозирования временных рядов

Algorithms
Sandbox
На написание статьи, подтолкнула публикация Прогнозирование временных рядов.

Здесь я покажу, как прогнозирование временных рядов может быть применено для увеличения поисковых способностей (ПС) генетических алгоритмов (ГА).

Читать дальше →
Total votes 29: ↑26 and ↓3 +23
Views4.3K
Comments 4

Генетические алгоритмы в MATLAB

AlgorithmsMatlab
Sandbox

Суть генетических алгоритмов


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

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

(Под катом основная часть + несколько скриншотов).
Читать дальше →
Total votes 64: ↑53 and ↓11 +42
Views49.6K
Comments 19

Генетический алгоритм на примере бота Robocode

DIY


Когда писалась эта статья, хабрапоиск по словосочетанию «Генетический алгоритм» выдавал благородную пустоту. Однако недостаточный уровень *вырезано цензурой* отодвинул дату публикации, и вот только сейчас после позорного нудливого попрошайничества с моей стороны эта статья получила возможность показать себя миру. За этот промежуток времени успели выйти в свет как минимум три (столько мне на глаза попалось) статьи на подобную тему, и, вполне вероятно, что-то из написанного ниже вы прочитаете не впервые. Таким людям я предлагаю не хмурить носики от очередной попытки неопытного юнца научно-популярно объяснить ГА, а проходить к следующему экспонату ко второй части, где описывается создание на основе ГА бота для программистской игры Robocode. Это, по последним сведениям разведки, еще не встречалось на хабре.

Часть первая. Жизнь и творчество генетического алгоритма.


Начнем издалека. Есть некоторый набор задач, которые требуют решения. Наша цель — найти действия, которые смогут преобразовать Дано (начальные условия задач) в Ответ (целевое состояние).

Если ситуация простая, и решение такой задачи можно явно посчитать из условий при помощи этих ваших матанов, то и славно, тут и без наших премудростей все хорошо, нас наебали, все расходимся. Например, при решении квадратного уравнения ответ (значения x1, x2) получаются из начального условия (коэффициентов a, b, c) путем применения формулы, которую мы все учили в школе. А что делать в более печальном случае, когда нужной формулы в учебнике нету? Можно попробовать с помощью мозгового штурма решить одну из задач. Аналитически. Численными методами. Силой отчаянного перебора функций. Через некоторое время послышатся мечтательное студенческое «хоть бы оно само решилось». Ага, тут-то мы и вылезаем из-за занавесок. Итак, цель — написать программу, которая бы находила функцию (программу), получающую на вход исходные данные и возвращающую годные циферки. Сила метапрограммирования, в бой!

пучина невежества
Total votes 115: ↑108 and ↓7 +101
Views25.4K
Comments 28

Выбор размера популяции для генетического алгоритма

Algorithms
Sandbox
Для души экспериментирую с генетическими алгоритмами.

Хотелось немного поделиться своим опытом, наблюдениями, размышлениями в небольшой серии очерков.

Итак, первый вопрос над которым задумался: какой размер популяции выбирать.
Если сформулировать этот вопрос системно, то он будет звучать так:

По какому принципу, исходя из каких критериев, рассчитывать размер популяции?
Добро пожаловать под кат
Total votes 30: ↑28 and ↓2 +26
Views13.4K
Comments 21

Генетический алгоритм: боремся с преждевременной сходимостью

Algorithms
В предыдущем очерке (Выбор размера популяции для генетического алгоритма) был определен минимальный размер популяции необходимый для работоспособности генетического алгоритма:
N = 1 + LOG2(1/(1-P1^(1/L))), где
P1 — требуемая вероятность того, что случайный набор хромосом будет содержать все необходимые элементы для каждого локуса;
L — длина хромосомы.

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

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

Сам собой напрашивается экстенсивный путь борьбы с этим явлением — увеличение размера популяции, но найти интенсивный (не ресурсозатратный) путь гораздо интересней.
Добро пожаловать под кат
Total votes 33: ↑30 and ↓3 +27
Views14.5K
Comments 23

Генетический алгоритм: оптимальный размер популяции

Algorithms
В предыдущем очерке (Генетический алгоритм: боремся с преждевременной сходимостью) в качестве эффективного метода борьбы с преждевременной сходимостью было выбрано использование оператора митоза:

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

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

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


далее небольшой анализ выбора оптимального размера популяции
Total votes 26: ↑24 and ↓2 +22
Views6.9K
Comments 11

Генетический алгоритм. Просто о сложном

Algorithms
Sandbox
Tutorial

В последнее время все больше «ходят» разговоры про новомодные алгоритмы, такие как нейронные сети и генетический алгоритм. Сегодня я расскажу про генетические алгоритмы, но давайте на этот раз постараемся обойтись без заумных определений и сложных терминах.
Как сказал один из великих ученных: «Если вы не можете объяснить свою теорию своей жене, ваша теория ничего не стоит!» Так давайте попытаемся во всем разобраться по порядку.
Читать дальше →
Total votes 74: ↑55 and ↓19 +36
Views245K
Comments 40

Генетические алгоритмы. От теории к практике

Algorithms
Sandbox
Добрый день. В последнее время решил заняться самообразованием. Решено было начать с генетических алгоритмов.

Одно из замечатльных свойств ГА это то, что процедуры Селекции, Скрещивания и Мутации представления не имеют о Индивидах в Поколениях — для них это всего-лишь 0 и 1. Единстенная функция, которая знает, что же из себя представляют эти самые 0 и 1 — это ФитнессФункция.

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

Кому интресно, прошу под кат.
Читать дальше →
Total votes 48: ↑40 and ↓8 +32
Views56.9K
Comments 36

Распределенные эволюционные вычисления

Algorithms


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

Сегодня я постараюсь объяснить генетические алгоритмы проще и нагляднее, а заодно рассказать вкратце о прототипе очень простого JavaScript-фреймворка для распределенных генетических вычислений degas.js. В двух словах – degas.js запускает генетический алгоритм в виде «треда» в браузере клиента используя web workers и обменивается информацией о полученных в ходе эволюции индивидуумах с сервером и другими клиентами с помощью web sockets. Сервер использует node.js.

Degas.js пока в супер-зародышевом состоянии, функционал еще примитивен, а код некрасив, но если кто-то захочет присоединиться к разработке – было бы здорово.
Total votes 31: ↑30 and ↓1 +29
Views4.9K
Comments 5

EvoJ — удобный фреймворк для генетических алгоритмов

Algorithms
Sandbox
Здравствуйте, коллеги!

Здесь часто появляются статьи на тему генетических алгоритмов, разрешите и мне внести свои пять копеек.

Вот уже пару лет я виде хобби разрабатываю Java-фреймворк EvoJ посвященный ГА. Когда я только начинал работу с ГА самое большое неудобство представляла необходимость векторизации переменных составляющих решение, поэтому в своем фреймворке я постарался сделать векторизацию переменных прозрачной для программиста, возложив всю грязную работу на плечи фреймворка. Кроме того, так как ГА очень хорошо поддается распараллеливанию, я постарался сделать переход к многопоточности не менее легким.
Читать дальше →
Total votes 34: ↑33 and ↓1 +32
Views5K
Comments 10

Упаковка в контейнеры (bin packing) при помощи генетического алгоритма

Algorithms
Доброго времени суток, коллеги.
Этой статьей я продолжаю цикл посвященный EvoJ — Java фреймворку для решения задач генетическим алгоритмом.
В своей предыдущей заметке я познакомил читателей Хабра с основными принципами работы с EvoJ.

Сегодня мы рассмотрим, как при помощи EvoJ можно решить задачу упаковки в контейнеры.
Читать дальше →
Total votes 25: ↑24 and ↓1 +23
Views13.9K
Comments 4