Ликвидатор велосипедов, часть 3: языки программирования. Велосипед программирование


Индустрия it-велосипедов / Хабрахабр

Введение
Я точно не могу сказать, что заставило написать этот пост — может быть мой накопившийся опыт и принадлежность к php-программистам, которые, всемирно известны своим быдлокодом или недавний пост, в котором автор описывает проблему, появившуюся в его велосипеде и связанную с глобальными переменными в различных модулях. 

Почитав комментарии к которому, мне стало уж совсем плохо… Я просто не понимал как люди не видят сути проблемы, а видят только лишь ее последствия — проблему в велосипеде. А суть то заключается в том, что у автора напрочь отсутствуют какие-либо познания в «велосипедостроении». И что самое страшное — эти знания отсутствуют не у одного него. А практически у всей массы изобретателей которые сами велосипеды видели только на картинках. 

А если взять в расчет то, что они не хотят даже посмотреть на другие велосипеды…  

Часть первая. История одного велосипедиста

Я думаю начать нужно с того, что следует мысленно вернутся к той планке опыта молодого велосипедостроителя, на которой я впервые столкнулся с трудностями. На полтора года назад — в снежную зимнюю ночь и мою комнату, освещенную 19-ти дюймовым элт-монитором, тихой депрессивной музыке, доносившейся из недр старого советского проигрывателя пластинок и собственно мне — сидящим на полу и высекающему медиатором на не подключенном семиструнном Ibanez'е. 

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

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

Поэтому я на отлично сдал диплом, тема которого звучала примерно так «CMS с использованием технологии AJAX», и так же как и многие пыхари, решил создавать свой велосипед. Я был полон энтузиазма, и мне не терпелось наконец-то собрать воедино все свои знания о современном велосипедостроении: парадигме объектно ориентированном программирования, технологии ajax, блочной верстки с использованием CSS и даже связку xml с xslt. 

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

Дрезина Макмиллана велосипед Пьера Лалмана Идеальный велосипед в понимании среднестатистического пыхаря
Но тогда мне казалось, что я изобретаю, современный mtb-хардтейл на усиленной дёртовой раме, гидравлическими дисковыми тормозами, мультиспидом и достаточно легким весом. Что бы можно себя комфортно чувствовать как в кросс-кантри, не беспокоясь за то, что можно где-нибудь застрять посредине леса. Так и на улицах города, занимаясь стритом, даже не думая о том, что он может сложится под тобой при неудачном прыжке с лестницы.
mtb-хардтейл

Этому способствовало еще и мое окружение, состоящее из таких же пыхарей, разных возрастов. У некоторых из них был опыт гораздо больший нежели у меня. И все они твердили одно и тоже: «Надо писать свою cms», «Зачем мне пользоваться чужим фреймворком если я способен написать его сам» и «Веб — сомнительное место для объектно ориентированного подхода, где время жизни скрипта не больше чем одна пятая секунды». 

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

Но я учился. И упорно следовал этим бездарным указаниями. Пиши свой велосипед крутилось в моей голове. ПИШИ! Я и писал. Опыта конечно у меня становилось все больше — картинки с различными велосипедами встречались все чаще и чаще, они становились больше, поэтому на них можно было разглядеть и некоторые детали. Да и узнал я о такой штуке как шаблоны проектирования. 

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

Сейчас то я понимаю, что трактовал эти шаблоны не совсем правильно — я воспринимал их как серебряную пулю, которая в идеале решает все проблемы, с которыми сталкивались люди до меня. И владея ей, я с легкостью мог создавать сложные приложения за очень короткий срок, даже не думая о том, что смогу наступить на неизвестные грабли- все уже решено до меня.  Это до меня люди наступали на грабли. До меня они больно бились головой о стены, пока не нашли правильный путь. А мне стоит только лишь пройтись по нему — вот и все. 

И я начал писать с использованием их. А знал я их порядка 15 штук. Вы знаете что такое эффект второй системы? Если нет, то представьте себе bmx с 20 дюймовыми шипованными колесами, рулем от шоссейного велосипеда, двумя амортизаторами, четырьмя гидравлическими тормозами по два на каждое колесо (дисковые и v-brake), поддерживающими боковыми колесами (для тех кто только учится ездить), тремя сиденьями, бардачком для инструментов, коляски сзади, планетарным механизмом переключения передач, контактными педалями, четырьмя фарами работающих от автомобильного аккумулятора, зеркалами заднего вида и ремнем безопасности. 

обыкновенный bmx
А если это все заставить держатся на одном огромном объектно-ориентированном гвозде — Registry, благодаря которому мы точно не можем сказать сможет ли ездить этот велосипед, если мы захотим снять один из фонарей… то получим точную копию созданной мной системы…

Продолжение следует.

Часть вторая. Продолжение

Я не буду удивлен если многие программисты увидят в этой истории самих себя. Тем более я не удивлюсь, если они увидят себя в самом начале этого пути — в окружении пыхарей, которые советуют изобретать, изобретать и еще раз изобретать. Забывая о том, что для того, что бы создать что-то новое. Необходимо понимать как работает. Умные люди этот момент понимают. 

Я даже приму как должное если вы дочитав до этой строчки ловите себя на мысли о том, что я вот с высоты своего опыта, который вы наверное уже поставили под сомнение, пытаюсь сказать «Изобретение велосипедов — зло». Пользуйтесь существующими. Нет. Тогда мы вернемся опять к уровню обезьян, а может быть даже и обратно в море.

Но давайте все разложим по полочкам.

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

И так проблема лежащая на первой полочке предельно проста  - низкий уровень вхождения. Научится изобретать все новые мутанты-велосипеды может любой человек за очень короткое время. К сожалению решить ее не просто. Просто так взять и поднять уровень вхождения в язык — практически невозможно. Причины вы и сами можете назвать.

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

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

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

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

Часть четвертая. Начинаем с нуля. 

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

И я начал учится. С нуля. По два-три часа в день, которые я нашел благодаря тому, что стал уделять меньше времени всему, что меня окружало — друзьям, любимым, музыке. И за это время я заново для себя открыл такие понятия как абстракция, полиморфизм. Я наконец-таки понял зачем нужно наследование, когда его следует применять, а когда вместо него необходимо использовать инкапсуляцию. Я заново открыл для себя объектно ориентированное программирование. 

До меня дошло что то, что написано в учебниках годится только для написания глупых оторванных от реальности примеров с яблоками и геометрическими фигурами. Я понял что объект — это какая сущность, она не привязана к реальным объектам. У нее есть свое состояние, обязательства перед другими сущностями и потребности в других объектах. Это так просто. Это написано в каждом учебнике по программированию. Первыми строчками. Они дают нам понимание что такое объектно ориентированное программирование, а потом забирают его примерами с квадратом наследованным от прямоугольника. И человек привыкает считать что объект — это что-то из реального мира. А после вопит «наплодили тут объектов», когда встречает грамотный объектно ориентированный код. Ему приходится ломать свое понимание этого подхода. Так же как сломал его и я. 

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

Во многом благодаря различным книгам по проектированию (которые легко читаются во время поездки в метро) и копанию в чужих велосипедах (zend, ci, symfony), я понял, что не всегда использование планетарного механизма переключения передач, который идеально подходит для городских прогулок (который я могу собрать и разобрать с утра, с закрытыми глазами и жутким похмельем), гораздо лучше обычного механизма с кучей звезд. Я даже понял, что иногда он вообще не нужен. Зачем bmx'у с десяток скоростей. Чтоб банники дергать на скамейку было проще? Или занимала флетлендом (по сути танцы с велосипедом). 

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

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

Заключение

В заключение хотел бы извинится перед  теми, кто считает, что я его задел, а среди таких я думаю наберется достаточное количество грамотных разработчиков со своими довольно грамотными велосипедами, на которых был поднят не один хороший проект. Речь шла все таки не о вас. Вас пыхарями назвать нельзя  :)

Сейчас это уже не так. Сейчас он уже собран во один единственный «чертеж», в котором я оставил только лишь интерфейсы для каждого компонента вместе с эксепшнами. Безжалостно удалив все то, что когда-то было написано и лишив старого названия(brix framework), которое, думаю, только сейчас будет наиболее точно отражать его суть: brix от того, что briks (кирпичи), а не мера массового отношения растворённой сахарозы, как говорит нам википедия. 

 

habrahabr.ru

О великих велосипедах, или почему иногда нужно писать с нуля / Хабрахабр

Not invented here — источник инноваций и причина успеха?

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

Очень часто в компаниях выступают против синдрома «not invented here». Я, как менеджер проектов, прекрасно понимаю соображения такого толка. Велосипеды — это лишние затраты, удлинение сроков разработки, сложность и дороговизна поддержки продукта в будущем, зависимость от разработчиков велосипеда и все такое прочее.

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

Не случайно поэтому Гугл выделяет 20% на свободное творчество, и это рождает такие великолепные переосмысления старых вещей, как почтовый клиент Gmail.

Но обо все по порядку. В этой статье я хочу коротко рассказать о трех «велосипедах», которые произвели революцию в своей области.Велосипеды и инновации часто ходят рядом — иногда в буквальном смысле

Ford Model T

Если бы я слушал своих клиентов, мне бы пришлось дать им более быструю лошадь Генри Форд, выдающийся предприниматель и изобретатель.

В начале 20го века производство автомобилей было ручным. Каждую операцию производили индивидуально. Также автомобили были очень дорогими, потому что было много разных настроек в «конфиге» сборки, и это приводило к издержкам.

Форд изменил ситуацию в корне, пойдя против сложившихся представлений, и изобрел велосипед. Во-первых, он выбросил все дополнительные опции, сказав известную фраза «любой клиент может получить автомобиль выкрашенный в тот цвет, в который он хочет — до тех пор пока этот цвет — чёрный».

Но что еще более важно, он первым запатентовал и стал использовать промышленный конвейер для сборки, в сотни раз повысив эффективность производства. О чем рассказал в известной книге "«Моя жизнь, мои достижения».".

Изобретательность Форда сделала автомобиль из предмета роскоши обычным, доступным для американского среднего класса средством передвижения.Впрочем, не все попытки бывают удачными и могут просто ехать, не говоря уже о взлете.

Google

Компания Google является примером фантастически удачной корпорации, сочетающей инновационность своих продуктов с коммерческим успехом.

Однако в начале 2000х, когда они только начинали, ситуация на рынке поисковых систем была совершенно иной. Сегодня Google — лидер и монополия. А тогда царили Yahoo, Altavista, Hotbot, Lycos и ряд других поисковиков, о которых помнят теперь только зубры интернета (хотелось сказать, древнее только фидо, но это было бы ложью)

Казалось бы, стоит ли изобретать велосипед, когда на рынке столько успешных корпораций. Однако Сергей Брин так не думал, напротив, он активно интересовался тематикой, сделал ее сначала объектом своих научных исследований. А затем и вместе с будущим партнером Ларри Пейджем написал прототип поисковой системы в рамках университета, из которого затем и выросла сверхуспешная компания, пережившая крах доткомов и победившая всех своих конкурентов.

Google набирал и набирает только лучших, и поддерживает дух энтузиазма и творчества, что несовместимо с запретом на создание своих велосипедов. 20% времени выделяется сотрудникам на создание своих проектов, и это дало свои плоды неоднократно.

nginx

Осенью 2001 года у меня появилась идея написать более легкий и производительный веб-сервер, чем Apache. На тот момент были уже другие похожие серверы, но все они не умели проксировать, они отдавали только статику. Был у них еще один общий недостаток – они работали в одном процессе, и, соответственно, отмасштабировать их, допустим, на двухпроцессорной машине было нереально. На тот момент у меня уже был достаточно неплохой опыт работы с Apache — и как у системного администратора, и как у программиста. Два написанных модуля прибавили мне знаний: приходилось смотреть исходники Apache и понимать, как там все устроено. Поэтому очень многие вещи в nginx перекочевали из Apache идеологически. Не код, а именно идеология, весь код nginx был написан с нуля. Из интервью выдающегося разработчика Игоря Сысоева

Каких только вариаций веб-сервера на Хабре не было — и на PHP, и на bash, и чуть ли не на Brainfuck (хм, а может не было? надо проверить! :) ).

Но по-настоящему серьезных разработок крайне мало. Ведь в сфере веб-серверов, казалось бы, все давно решено — есть проверенный годами Apache, есть всякие Томкаты для Джавы, для MS есть свой IIS, в общем, выбирай — не хочу. И взяться разработать веб-сервер, который в будущем не просто обойдет apache, а даже местами вытеснит его (многие ставят nginx +php-fpm без апача) — это не просто дерзко, это просто неслыханно!

Но, тем не менее, велосипед был написан, и достиг впечатляющих результатов (100 тысяч соединений, Фря, nginx, масло, 2007).

Слова выдающегося инноватора актуальны и поныне.

%имя Вашего проекта%

К чему все эти истории? Вам может казаться, что написать велосипед — это лишнее. Начальство может успешно промывать мозги, что писать свои компоненты не нужно, нужно все брать готовое. Друзья говорить, что уже написано 10 фреймворков (серверов, шифраторов, поисковых систем, архиваторов, собрано марсоходов и тд), и что ваша затея не имеет смысла.

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

Найдите то, что Вам по душе. И создайте нечто свое, новое, что можно показать миру. Ведь если все будут собирать продукты из кубиков лего и копировать друг у друга, кто будет двигать мир, как не изобретатели велосипедов?

Invent it all again!

upd: в комментариях увидел жалобы на отсутствие определения «велосипеду». Общего определения однозначного, как известно, не существует. Дам свое.

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

Никаких сомнений, что nginx является велосипедом в таком понимании, нет — это веб-сервер, пусть и отличный по архитектуре и содержающий новые идеи. Но уже __были__ веб-сервера, и все-же Сысоев написал nginx с нуля, за что ему огромное спасибо и низкий поклон. И поисковики уже были до Гугла, и машины тоже делали до Форда.

habrahabr.ru

Ликвидатор велосипедов, часть 3: языки программирования / Хабрахабр

Вообще говоря, речь пойдет о разработке компиляторов не Just for fun, а для каких-либо проектов. Это могут быть проекты для внутреннего использования, или может быть это будут проекты, которые направлены на продажу. А может быть, на самововлечение сообщества для последующего доения этого сообщества. Я не буду разбирать причины, по которым может показаться, что создание нового языка программирования выведет компанию на новый уровень, однако причины находятся, языки пишутся, создавая, на мой взгляд, огромные проблемы, как самой компании, так и сотрудникам этой компании.

Ссылка на первую часть серии: оконные системы Ссылка на вторую часть серии: построение графиков Во-первых, разработка собственного языка программирования может начаться, просто потому что автору кажется, что этот язык (для кого-то, а в идеале – для всех) будет лучше остальных. Ну, мы-то с вами понимаем, что в 99,9% случаев эта идея утопична.

Далее может быть такая ситуация что руководство, купив новое железо, или что лучше – разработав новый тип устройства, вдруг решило что все что есть – не подойдет и надо что-то придумать. Например, новый язык программирования под этот, доселе не известный 80386С.

Также вполне часто-встречаема ситуация, когда есть разработчик, который хочет увековечить себя в компании и делает все что может, лишь бы быть не заменимым… Свой компилятор, своя операционная система, свои драйвера, приблуды командной строки… Чтобы справка обозначалась на знаком вопроса а комбинацией Ctrl+Alt+LOLS. Короче говоря, чтобы никто кроме него самого здесь понять ничего не мог. Тогда-то его будут ценить, повышать зарплату. Ведь никто не захочет вкладывать деньги в процесс переделки того что уже есть.

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

Откровенные минусы такого подхода:

  1. Вместо того чтобы потратить неделю на поиски и 3 недели на изучение, компания тратит года на разработку и сопровождение компилятора и сопутствующего ПО;
  2. Невозможно найти высококвалифицированных работников под язык, который нигде больше не используют;
  3. Персонал, который все таки нанимается, не получает опыта. Это люди, которые теряют навыки. Если человек до этого писал на платформе .NET, то через некоторое время он забудет библиотеки, а потом и сам язык C#.
Отсюда вытекают выводы, что в любом случае просто необходимо немного подумать и решить что такое решение – пустая трата времени и денег для компании. Если Вас по какой-то причине штат программистов уверяет в необходимости такого шага, значит либо они хотят стать не заменимыми в компании, а значит – поставить вас в зависимость от них, либо у них слишком низкая квалификация.

Самым универсальным способом использовать современные технологии в своих устройствах будет либо ручная сборка, либо поиск готового решения операционной системы Linux. В общем, наверное, я не вижу смысла брать что-то еще. В этой системе у вас будет все, что надо для жизни. В качестве среды разработки может выступить любая IDE (например, Eclipse SDK). Отладку можно проводить через JTAG. Поддерживаются практически все процессоры, которые есть в мире. Компилятор GCC даст возможность писать на C/C++ под любой из этих процессоров программное обеспечение для вашего устройства. Также вы можете писать под любое устройство, используя язык программирования C#. А вместе с ним – все библиотеки фреймворка. Единственное – может быть вам придется добавить немного памяти на устройство. Задачу можно осуществить при помощи проекта Mono. Помимо экзотичного на Linux C#, вы можете использовать более традиционные языки, благо под Linux имеется их богатая поддержка.

Помимо Linux на железо прекрасно ставится Java (J2ME) и Windows CE, но с этим вопросом я знаком слабо, советую почитать соответствующую литературу.

Если говорить о разработке нового языка программирования в рамках какого-либо десктопного приложения, то это, на мой взгляд, оправдано только если язык направлен на узко-квалифицированных специалистов, и такого языка еще не было. Если вы создаете программный продукт, уступающий по функционалу существующим аналогам, например, хотите составить конкуренцию MathCAD или MetaTrader 4, то лучший путь здесь – либо поддержать их языки программирования, либо поддержать любой из существующих языков программирования. Поскольку разработка компиляторов, оснащения языка богатым инструментарием, отладка полученного кода займет столько времени, что вы просто проедите весь существующий бюджет, и у вас ни на что не останется денег. А, поверьте, вы должны будете сделать еще и конкурирующий продукт. Причем так его сделать, чтобы пользователь поверил вам что его стоит покупать и использовать.

Как быстро составить конкуренцию торговой платформе?

  1. В ядре — TPL, DLR, MEF
  2. Плагинная модель — MEF, конфигурация на XML
  3. Оконная модель — см часть 1
  4. Графики — см часть 2
  5. Окно редактирования кода скрипта — SharpDevelop 3.X — там можно выцепить и редактор и отладчик и компиляцию.
  6. Язык программирования — C#, VB.NET, IronPython, IronRuby, любой .NET — совместимый.
Поверьте, этого вам хватит для сверхбыстрого старта. Сервер пишем на C# под любую свободную или платную БД. В итоге получаем быстро разработанный продукт, сокращенные как минимум на год сроки разработки и автоматическую поддержку сообщества, знающих те языки программирования, которые вы выбрали в качестве скриптовых для вашей платформы. Если вы все-таки решили написать свой велосипед, такой автоматической поддержки у вас не будет. Здесь вы сами себе враг.

habrahabr.ru

Генетическое программирование («Yet Another Велосипед» Edition) / Хабрахабр

Давайте на время отвлечемся от очередного "языка-убийцы C++", ошеломляющих синтетических тестов производительности какой-нибудь NoSQL-ой СУБД, хайпа вокруг нового JS-фреймворка, и окунемся в мир "программирования ради программирования".

Предисловие

Март начинался для меня с чтения статей про то, что Хабр уже не торт. Судя по отклику, тема была вскрыта наболевшая. С другой стороны, мне удалось кое-что для себя вынести из этого: "вы и есть Сопротивление", если вы это читаете — вы и есть Хабр. И сделать его интереснее (или хотя бы разнообразнее, отойти от наметившейся тенденции на агрегацию рекламных постов, околоализарщины и корпоративных блогов) можно только силами рядовых пользователей. У меня как раз имелся на тот момент небольшой проект, хоть и требующий серьезной доработки, о котором мне захотелось рассказать. И я решил — за месяц (наивный!) напишу статью. Как мы видим, сейчас уже середина конец апреля начало мая май в самом разгаре, винить в этом можно как мою лень, так и нерегулярность свободного времени. Но всё же, статья увидела свет! Что интересно, пока я трудился над статьей, уже успели выйти две похожие: Что такое грамматическая эволюция + легкая реализация, Символьная регрессия и еще один подход. Не будь я таким слоупоком, можно было вписаться и объявить месяц генетических алгоритмов :)

Да, я осознаю в полной мере, что на дворе 2016 год, а я пишу такой длиннопост. Ещё и рисунки выполнены в стиле "курица лапой" пером на планшете, с шрифтами Comics Sans для гиков xkcd.

Введение

Некоторое время назад на ГТ появилась интересная статья, с, что характерно, ещё более интересными комментариями (а какие там были словесные баталии об естественном отборе!). Возникла мысль, что если применить принципы естественного отбора в программировании (если быть точнее, то в метапрограммировании)? Как вы можете догадаться, эта мысль в итоге и привела меня к переоткрытию давно существовашей концепции генетических алгоритмов. Бегло изучив матчасть, я с энтузиазмом ринулся экспериментировать. Но давайте обо всём по порядку.

Ликбез

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

Как с помощью генетических алгоритмов решать задачи? Вы удивитесь, как всё просто работает в нулевом приближении:

Теперь WE NEED TO GO DEEPER. Первое приближение:

Значит, у нас есть задача\проблема, мы хотим найти её решение. У нас есть какое-нибудь базовое, плохенькое, наивное решение, результаты которого нас, скорей всего, не удовлетворяют. Мы возьмём алгоритм этого решения и немного изменим его. Натурально случайным образом, без аналитики, без вникания в суть проблемы. Новое решение стало выдавать результат хоть на капельку лучше? Если нет — отбрасываем, повторяем заново. Если да — ура! Удовлетворяет ли результат нового решения нас полностью? Если да — мы молодцы, решили задачу с заданной точностью. Если нет — берем полученное решение, и проводим над ним те же операции. Вот такое краткое и бесхитростное описание идеи в первом приближении. Впрочем, думаю, пытливые умы оно не удовлетворит.

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

Теперь давайте рассмотрим основной цикл подробнее:

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

  • Генетические операции (да-да, извечная путаница с переводом, английское "operator" суть наше "операция") нужны чтобы получить новое решение на базе предыдущих. Обычно это скрещивание (случайное совмещение двух различающихся решений) и мутация (случайное изменение одного решения).
  • Функция приспособленности (мне больше понравилось фитнесс-функция) нужна для оценки степени нашей удовлетворенности результатом решения.Кому на ум пришло TDD?

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

  • Селекция описывает принципы отбора решений в следующее поколение.

Недостатки

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

Практика

Выбор языка

Был выбран Ruby. Этот язык заполнил в моих делах нишу, каковую традиционно занимал Питон, и он настолько меня очаровал, что я непременно решил познакомиться с ним поближе. А тут такая возможность! Люблю убивать N (где N > 1) зайцев за раз. Не исключаю, что мой код может местами вызывать улыбки, если не фейспалмы у олдовых рубистов (нет, извините, но именно рУбистов, остальные варианты — троллинг).

Генотип

Первой мыслью было то, что раз в языке есть eval, то генотип решения может без каких-либо ухищрений строиться из произвольных символов (выступающих в роли генов), и на выходе мы будем иметь скрипт, интерпретируемый самим Ruby. Второй мыслью было то, что на эволюцию решений с такими высокими степенями свободы может уйти реально много лет. Так что я даже не шевельнул пальцем в этом направлении, и думаю, не прогадал. Можно попробовать данный подход лет этак через 30, если сохранится закон Мура. Эволюция в итоге была заключена в достаточно жесткие рамки. Генами решения являются высокоорганизованные токены с возможностью вложенности (построения древовидной структуры). В первом эксперименте, где мы будем говорить о решениях как математических выражениях, токены это константы, переменные, и бинарные операции (не знаю, насколько легитимен термин, в контексте проекта "бинарная операция" значит действие над на двумя операндами, например сложение). Кстати, я решил частично оставить совместимость с eval, поэтому если запросить строковое представление токена (через стандартный to_s), то можно получить вполне удобоваримую строку для интерпретации. Например:

f = Formula::AdditionOperator.new(Formula::Variable.new(:x), Formula::IntConstant.new(5)) f.to_s # "(x+5)"

Да и нагляднее так.

Генетические операции

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

  • Иногда (на самом деле часто) бывает, что лишь за один шаг мутации невозможно добиться улучшения результатов, хотя мутация идет, в целом, в верном направлении. Поэтому в фазе применения генетических операций решениям позволено мутировать неограниченное количество раз за ход. Вероятность выглядит так: — 50% — одна мутация — 25% — две мутации — 12.5% — три мутации — и т.д.
  • Бывает, за несколько шагов мутант может стать идентичным родителю, или разные родители получают одинаковых мутантов; такие случаи пресекаются. Более того, я вообще решил поддерживать строгую уникальность решений в рамках одного поколения.
  • Иногда мутации порождают совершенно неработоспособные решения. С этим бороться аналитически крайне сложно, обычно, проблема вскрывается только в момент их оценки фитнесс-функцией. Я позволяю таким решениям быть. Всё равно бОльшая часть со временем исчезнет в результате селекций.

Фитнесс-функция

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

  • вычисляет насколько результаты решения отличаются от эталонных
  • определяет, насколько ресурсоемко решение
О ресурсоемкости

В ранних прототипах я пробовал замерять затраченное на прохождение испытаний процессорное время, но даже при длительных (десятки миллисекунд) прогонах наблюдался разброс в ±10% времени на одно и то же решение, вносимый операционной системой, с периодическими выбросами +в 100-200%. Так что в первом эксперименте ресурсоемкость вычисляется суммарной сложностью генотипа, а во втором подсчётом реально выполненных инструкций кода

Селекция

Каждое поколение содержит не более чем N решений. После применения генетических операторов, у нас максимум 2N решений, притом в следующее поколение пройдет, опять же, не больше N из них. По какому принципу формируется следующее поколение решений? Мы на этапе, когда каждое из решений уже получило оценку фитнесс-функции. Оценки, разумеется, можно сравнивать друг с другом. Таким образом, мы можем отсортировать текущее поколение решений. Дальше видится логичным просто взять X лучших решений, и сформировать из них следующее поколение. Однако, я решил не останавливаться на этом, и включать в новое поколение также Y случайных решений из оставшихся. Например, если X = Y, то чтобы решению пройти в следующее поколение, ему нужно оказаться среди 25% лучших, либо выкинуть 3 на трёхгранном кубике (если бы такой существовал). Достаточно гуманные условия, не так ли? Так вот, включение случайно выживших в следующее поколение нужно для сохранения видового многообразия. Дело в том что подолгу держащиеся среди лучших похожие друг на друга решения выдавливают остальные, и чем дальше, тем быстрее процесс, а ведь зачастую бывает что доминирующая ветвь оказывается тупиковой. Параметры X и Y, разумеется, являются настраиваемыми. Я прогонял тесты, как со случайными выжившими, так и без них, и доказал справедливость их добавления в алгоритм: в отдельных случаях (при поиске решений повышенной сложности), удавалось достичь более хороших результатов с их использованием (притом суммарная затрачиваемая на поиск решений мощность оставалась постоянной, например, X1 = 250, Y1 = 750 против X2 = 1000, Y2=0).

Условия победы

Тут кроется загвоздка: как понять, что пора заканчивать? Допустим, решение удовлетворяет нас по точности результатов, но как быть с трудоемкостью? Вдруг алгоритм сейчас поработает и выдаст решение по раскраске графов за O(n)? Утрирую конечно, но критерий остановки работы необходимо формализовать. В моей реализации выполнение алгоритма заканчивается, когда Top 1 решение не меняется определённое количество поколений (сокращенно R — rounds). Отсутствие ротации значит, что, во-первых, не нашлось альтернативного решения, которое бы смогло превзойти лучшее текущее решение; во-вторых, лучшее текущее решение не смогло породить улучшенную мутацию себя в течение заданного времени. Количество поколений, через которое наступает победа лучшего решения, обычно большое число — чтобы действительно убедиться в том, что эволюция не способна продвинуться дальше, требуется смена нескольких сотен (число варьируется в зависимости от сложности самой задачи) поколений. К сожалению, несмотря на многочисленные предосторожности, случаи когда эволюция заходит в тупик всё же бывают. Это известная проблема генетических алгоритмов, когда основная популяция решений сосредотачивается на локальном оптимуме, игнорируя, в итоге, искомый глобальный оптимум. На это можно ответить игрой с параметрами: уменьшением квоты для победителей, увеличением квоты для случайных, и увеличением времени доминирования для победы, параллелизацией независимых друг от друга поколений. Но всё это требует мощностей\времени.

Конкретная реализация

Как принято, всё выложено на гитхабе (правда, пока без доков). Теперь о том, что мы увидим в конкретно моей велосипеде реализации:

  1. Вводится понятие эталона (Model). Относимся к нему, как к чёрному ящику, с помощью которого, на основе набора входных данных (Input), можно получить эталонный результат(Model Result).
  2. Дело (Case) попросту содержит набор входных данных и эталонный результат.
  3. Собираем набор дел (Case group) на основании совокупности входных данных (Input group).

  4. Вызов (или испытание) (Challenge) это комплекс действий по прохождению сформированного ранее набора дел. На плечах испытания также работа по оценке результатов прохождения, и сравнению оценок.
  5. У нас появляется претендент (Challenger), имеющий определенное решение (Solution). Претендент произносит сакраментальное "вызов принят!", и узнает свою степень пригодности (Score).

  6. В итоге у нас выстраивается цепочка композиции — решение(Solution — предоставляет решение определенного вида задач) -> претендент(Challenger — проходит испытания) -> штамм(Strain — участвуют в естественном отборе и эволюции(см.ниже))
  7. Имеется естественный отбор (Natural Selection), который включает в себя испытание, и фильтрует поступающую к нему группу штаммов по заданным правилам.

  8. На верхнем уровне располагается эволюция (Evolution), которая, включая в себя естественный отбор, управляет всем жизненными циклом штаммов.
  9. Результатом работы эволюции является штамм-победитель, которого мы чествуем как героя, а затем внимательно изучаем его, в том числе и его родословную. И делаем выводы.

Такова в общих чертах моя реализация генетического алгоритма. За счёт абстрактных классов (в Ruby, ага >_<), удалось написать в целом независимый от конкретной области задач код. В последующих экспериментах дописывались нужные Input, Model, Solution, Score (что, конечно, немало).

Эксперимент Первый: Формулы

Вообще, вернее было назвать Эксперимент Первый: Арифметические выражения, но когда я выбирал имя для базового класса выражений, то, недолго думая, остановился на Formula, и дальше в статье я буду называть арифметические выражения формулами. В эксперименте мы вводим формулы-эталоны (та самая Model), содержащие одну или несколько переменных величин. Например:

x2 — 8*x + 2.5

У нас есть набор значений переменных (Input Group, ага), например:

  • x = 0;
  • x = 1;
  • x = 2;
  • ....
  • x = 255;

Решения (Solutions), которые мы будем сравнивать с эталонами, представляют из себя такие же формулы, но создаваемые случайно — последовательно мутирующие из базовой формулы (обычно это просто x). Оценкой (Score) качества решения является среднее отклонение результата от результата эталона, плюс ресурсоемкость решения (суммарный вес операций и аргументов формулы).

Мутация формул

Как было упомянуто ранее, токенами формул являются константы, переменные, и бинарные операции. Как происходит мутация формул? Она затрагивает один из токенов, содержащихся в формуле, и может пойти тремя путями:

  1. grow — рост, усложнение
  2. shrink — уменьшение, упрощение
  3. shift — видоизменение с условным сохранением сложности

Вот таблица происходящего с разными типами формул при разных видах мутации:

Формула → Мутация ↓ Константа Переменная Бинарная операция
grow становится переменной, или включается в новую случайную бинарную операцию (со случайным вторым операндом) в новую случайную бинарную операцию (со случайным вторым операндом) включается в новую случайную бинарную операцию (со случайным вторым операндом)
shrink невозможно уменьшить, так что применяем к ней операцию shift становится константой вместо операции остается лишь один из операндов
shift изменяет свое значение на случайную величину, может поменять тип (Float<->Int) становится другой случайной переменной (если это допустимо в данном контексте) либо операнды меняются местами, либо меняется вид операции, либо происходит попытка сокращения операции

Примечание 1 Сокращение формул это попытка заранее произвести операции над константами, где это возможно. Например из "(3+2)" получить "5", а из "8/(x/2)" получить "(16/x)". Задача неожиданно оказалась настолько нетривиальна, что вынудила меня писать прототип решения с исчерпывающим юнит-тестом, и то, я не добился настоящего рекурсивного решения, достающего константы для сокращения с любой глубины. Разбираться в этом было увлекательно, но в какой-то момент мне пришлось остановить себя и ограничиться достигнутым решением, так как я слишком отклонился от основных задач. В большинстве ситуаций, сокращение и так полноценно работает.Примечание 2 У мутации бинарных операций есть особенность, в силу того, что операции имеют вложенные в себя другие формулы-операнды. Мутировать и операцию, и операнды — слишком большое изменение для одного шага. Так что случайным образом определяется, какое событие произойдёт: с вероятностью 20% мутирует сама бинарная операция, с вероятностью 40% мутирует первый операнд, и с оставшейся 40% вероятностью, мутирует второй операнд. Не могу сказать, что соотношение 20-40-40 идеально, возможно следовало бы ввести корреляцию вероятности мутации операции в зависимости от их весов (фактически, глубины вложенности), но пока что работает так.

Результаты

Теперь ради чего, собственно, всё затевалось:

Первый эталон — простой полином:

x2 — 8*x + 2.5

X принимает значения от 0 до 255, с шагом 1R = 64, X = 128, Y = 128

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

Результаты поразили меня в самое сердце :) За 230 (включая те R раз, когда Top 1 не менялся) поколений было выведено такое решение:

(-13.500+((x-4)2))Полная родословнаяКак вы помните, между один поколением допускается и более одной мутации.x (x-0) ((x-0)-0.050) (0.050-(x-0)) (0.050-(x-1)) (x-1) (x-1.000) ((x-1.000)--0.010) ((x-1.000)-0) ((x-1.000)-(1*0.005)) ((x-1.000)/(1*0.005)) ((x-1.020)/(1*0.005)) ((x-1.020)/(0.005*1)) ((x**1.020)/(0.005*1)) ((x**1)/(0.005*1)) ((x**1)/(0.005*(0.005+1))) ((x**1)/(0.005*(0.005+1.000))) (x**2) ((x--0.079)**2) ((x-0)**2.000) (((x-0)**2.000)/1) (((x-0)**2)/1) ((((x-0)**2)-0)/1) (((x-0)**2)-0) (((x-0)**2)-0.000) (((x-(0--1))**2)-0.000) (((x-(0--2))**2)-0.000) (((x-(0--2))**2)+0.000) (((x-((0--2)--1))**2)+0.000) (((x-((0--2)--1))**2)+-0.015) (((x-((0--2)--1))**2)+0) ((-0.057+0)+((x-((0--2)--1))**2.000)) ((-0.057+0)+((x-3)**2.000)) (((-0.057+0)**-1)+((x-3)**2.000)) (((-0.057+0)**-1)+((x-4)**2.000)) (((-0.057+0)**-1.000)+((x-4)**2.000)) (((-0.057+0.000)**-1.000)+((x-4)**2.000)) (((x-4)**2.000)+((-0.057+0.000)**-1.000)) (((x-4)**2)+((-0.057+0.000)**-1.000)) (((x-4)**2)+((-0.057+0.000)**-0.919)) ((((x-4)**2)+((-0.057+0.000)**-0.919))+-0.048) ((((-0.057+0.000)**-0.919)+((x-4)**2))+-0.048) ((((-0.057+0.000)**-0.919)+((x-4)**2))+-0.037) (((-0.057**-0.919)+((x-4)**2))+-0.037) (-0.037+((-0.057**-0.919)+((x-4)**2))) (-13.524+((x-4)**2)) (-13.500+((x-4)**2))

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

  • R = 250, X = 250, Y = 750, Точность = 0.001, (вес результата 49) (2.500+((x-8)*x))
  • R = 250, X = 1000, Y = 0, Точность = 0.001, (вес результата 60)(((x-1)*(-7+x))-4.500)

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

Второй эталон — натуральный логарифм:

ln(1 + x)

x принимает значения от 0 до 25.5, с шагом 0.1 Наши решения лишены возможности использовать логарифмы напрямую, но данный эталон раскладывается в ряд Тейлора:

Вот и посмотрим, сможет ли решение воспроизвести такой ряд с заданной точностью. Поначалу, пробовал прогоны с точностью до 0.001, но после нескольких суток упорной работы алгоритма решения достигли точности только около 0.0016, а размер выражений стремился к тысяче символов, и я решил снизить планку точности до 0.01. Результаты таковы:

  • R = 250, X = 250, Y = 750, Точность = 0.01, (вес результата 149)((((-1.776-x)/19.717)+(((x*x)-0.318)**0.238))-(0.066/(x+0.136)))
  • R = 250, X = 1000, Y = 0, Точность = 0.01, (вес результата 174)(((-0.025*x)+(((x*x)**0.106)**2))/(1+(0.849/((x*x)+1))))

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

Третий эталон — синус, задаваемый в радианах:

sin(x)

x принимает значения от 0 до 6.28, с шагом 0.02 Опять же, эталон раскладывается в ряд Тейлора:

В данном случае, учитывая что при любом x результат принимает значение от -1 до 1, точность определения в 0.01 была более серьёзным испытанием, но алгоритм справился.

  • R = 250, X = 250, Y = 750, Точность = 0.01, (вес результата 233)((((-0.092**x)/2.395)+(((-1.179**((((x-1)*0.070)+-0.016)*4.149))-(0.253**x))+0.184))**(0.944-(x/-87)))
  • R = 250, X = 1000, Y = 0, Точность = 0.01, (вес результата 564)(((x+x)*((x*-0.082)**(x+x)))+(((x+x)**(0.073**x))*((((1-(-0.133*x))*(-1-x))*((x/-1)*(-0.090**(x--0.184))))+(((((-1.120+(x*((x+1)*-0.016)))**(-0.046/((0.045+x)**-1.928)))+(-0.164-(0.172**x)))*1.357)**0.881))))

Опять же, ввиду повышенной сложности эталона, лучшего результата добилась версия алгоритма с пулом случайным решений.

Четвертый эталон — выражение с четырьмя (совпадение? не думаю) переменными:

2*v + 3*x — 4*y + 5*z — 6

Каждая из переменных принимает значения от 0 до 3 c шагом 1, всего 256 комбинаций.

  • R = 250, X = 250, Y = 750, Точность = 0.01, (вес результата 254)((y*0.155)+(-2.166+(((((z*4)-(((y-(x+(y/-0.931)))*2)+-0.105))+((v+(v-2))+-0.947))+x)+(z+-1))))
  • R = 250, X = 1000, Y = 0, Точность = 0.01, (вес результата 237)((-3+(v+z))+(((v+((x-y)+((((z+z)-(((0.028-z)-x)+(y+y)))-y)+z)))+x)+-2.963))

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

Итоги

В целом, я остался скорее не доволен полученными результатами, особенно, по эталонам 2 и 3. Понадобились тысячи поколений, чтобы вывести в итоге громоздкие формулы. Я вижу три варианта, почему это случается:

  1. Несовершенный механизм сокращения — например, не хватает более дальновидного раскрытия скобок\выноса за скобки. Из-за этого формулы не привести в удобный вид.
  2. Слишком спонтанная мутация, причем, чем больше формула, тем меньше вероятность правильного дальнейшего развития. Я подумывал о создании "исчерпывающего" (exhaustive) механизма мутации, когда формируется группа условно всех возможных мутантов на базе оригинала, и над ней производится пред-селекция. Дойдут ли руки проверить догадку, улучшит ли это алгоритм, пока неизвестно.
  3. Принципиальная непрактичность такого метода для нахождения решений сложных задач. Быть может, данный подход не так уж далеко ушел от попыток написать "Войну и мир" силами армии обезьян с пишущими машинками. Быть может, сложность, необходимость аналитического подхода, это природное и неотъемлемое свойство таких задач.Курьёз

    Вспомнил, как лет десять назад интересовался сжатием данных, пробовал силы в написании своего решения. Сокрушался, что никак не удается сжимать рандомные паттерны, пока меня не просветили :) Может, и здесь так?

Дальнейшие эксперименты

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

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

nil

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

Закончим на этой задумчиво неопределенной ноте. Большое спасибо за уделенное время!

habrahabr.ru


Смотрите также