Pull to refresh

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Artificial Intelligence


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

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

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

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

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

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

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

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

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



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

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

Algorithms *
Sandbox

Предисловие


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

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

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

Algorithms *

Предисловие


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

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

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

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

Ruby *

Предисловие


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

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

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

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

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

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

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

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

Algorithms *Matlab *
Sandbox

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


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

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

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

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

DIY


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

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


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

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

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

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

Algorithms *
Sandbox
Tutorial

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

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

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

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

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

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

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

Algorithms *


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

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

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

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

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

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

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

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

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

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

Ограничение оптимизирующих методов в играх с противником и без

Algorithms *
Эта статья короткое ответвление от цикла статьей по биовычислениям:
От белков к РНК, Мат. критерии, Как уменьшить число поворотов цепи?, Как оценить ход сворачивания односпиральной РНК?

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

Казалось бы сама физика велит использовать эти методы в таких задачах как сворачивание РНК/белков. Здесь мы посмотрим почему это сильно проблемно.

Читать дальше →
Total votes 19: ↑15 and ↓4 +11
Views 2.5K
Comments 5

Аппроксимация изображений генетическим алгоритмом при помощи EvoJ

Java *Algorithms *
В этой статье я расскажу, как можно применить генетический алгоритм для аппроксимации изображений полигонами. Как и в своих предыдущих статьях, использовать для этой цели я буду собственный фреймворк EvoJ, о котором уже писал здесь и здесь.


Читать дальше →
Total votes 18: ↑17 and ↓1 +16
Views 12K
Comments 22

Генерация дизайнерских идей при помощи генетического алгоритма

Luxoft corporate blog Programming *Algorithms *
Я, как и многие люди технического склада ума, испытываю трудности с рисованием и графическими решениями вообще. Я, конечно, могу отличить красивое решение от плохого, но оказываюсь в тупике, когда нужно нарисовать что-то с нуля, будь то пользовательский интерфейс приложения, презентация или открытка.
В своей прошлой статье я продемонстрировал, как можно использовать генетический алгоритм чтобы аппроксимировать изображение по заданному образцу. В этой статье, я покажу, как применить генетический алгоритм для генерации изображений «из головы».


Читать дальше →
Total votes 67: ↑62 and ↓5 +57
Views 29K
Comments 36