10 Jul 98 - dz online

В Чехии запустили уникальную телефонную службу. Пользователь сотовой телефонной компании RadioMobil путем набора определенного префикса может заказать проброс международного телефонного звонка через Интернет. Это обходится в 40 центов/минута при звонках в Европу и 60 - за ее пределы.

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

Лужков подхватил эстафету и тоже ринулся в пучины Интернета на целый час. Правда, тематика беседы была ограничена Юношескими Играми, но все же...

Увы, все эти беседы показывают, что час - это очень немного для Интернета, особенно, когда слуга народа не садится за компутер сам, а работает при помощи голосового интерфейса. Да и часа, собственно, не выходит. 21:34-22:28, и всего 10 вопросов прошло. Из более, чем 250 заданных. Жидэнько.

From:	Joseph V. Petviashvili
Subject:	Генетические Алгоритмы и Программирование

Привет!

То что ты написал в своей статье про генетические алгоритмы - замечательно. Но есть две основные причины, по которым они еще не прижились в коммерческой сфере:

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

Эффективность генетических алгоритмов объясняют двумя вещами:

Schema Theorem (Теорема о схемах)

На первый взгляд кажется что генетические алгоритмы просто один из методов перебора всех возможных вариантов, но можно посмотреть на дело с другой стороны. А именно: в ДНК те части (схемы), которые отвечают за конкретные свойства организма, конкурируют между собой, и более приспособленные получают больше шансов на размножение. Например: пусть ДНК это цепочка 0 и 1, а * обозначет любую цифру, то схемами могут быть *01**, 1**1*, ***01. Каждая схема может соответсвовать конкретному признаку, и тогда если этот признак полезен, то все генотипы, которые соответсвуют этой схеме получают преимущество, и с течением времени этой схеме будет соответвовать все большая часть популяции. Подразумевается что сами схемы короткие, и что самое главное, перекрестное влияние генов в ДНК слабое.
Building Block Hypothesis (Гипотеза о строительных блоках)

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

В природе все устроено замечательно и оба эти объяснения прекрасно все объясняют ;) Природа работает как истинно параллельный компьютер, причем достигается супер-линейная производительность (то есть эффективность растет с увеличением количества особей/процессоров) за счет дополнительной кластеризации популяции из-за всякой географии. Скорее всего есть и другие механизмы, которые обеспечивают эффективность эволюции в природе...

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

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

А про Азимовских роботов наверное все так и есть (если не придумают как складывать отдельные кирпичики вместе вручную).

Joe

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

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

Теперь о кодировании. Природа создала человека, НЕ применяя интеллекта. Если мы исходим из того, что Дарвин прав (а пользуясь генетическими методиками мы из этого автоматом исходим), проходится признать, что нужно только суметь ими овладеть не хуже природы, и интеллект можно нести в помойку. И использование генетики в применении к FPGA - шаг именно в этом направлении.

Да, и еще о параллельности. Распараллеливаемость процесса - это же дар богов, его лелеять надо. :-)

Написав вчера про Xeon, я как-то в стороне оставил сам процессор. Незаслуженно. Коротко говоря, это коробка на базе Slot II, в ней - Pentium II core, 0.5, 1 или 2 мегабайта кеша второго уровня, и все это ( и процессор, и кеш второго уровня) работает на 400 или 450 МГц. Повторю на случай невнимательного прочтения - до двух мегабайт кеша второго уровня на частоте кристалла.

Далее. Внешняя шина - 100 Мгц. Встроенная поддержка мультипроцессорности - до 4-х процессоров, внешними средствами можно посадить на одну шину и больше. Разрабатываются схемы с 6-ю и 8-ю процессорами, к примеру.

Интересный момент. Добавление в машину второго Xeon-а увеличивает ее стоимость на 10-15%, а производительность - на 70-80%. Счетную, конечно.

В Xeon реализована 36-разрядная адресация памяти, отсюда максимальный объем вырос до 64 Gb. Оперативки, напомню. В серверах, для которых предназначен этот процессор, старый предел объема ОЗУ в 4 Gb уже представляется недопустимым.

Штатный chipset для ксеона - Intel 450 NX. До трех шин PCI (одна - 64 разряда, две - по 32 разряда), до 8 Gb адресуемой памяти, 1-4 процессора.

На Митинском вовсю продают BeOS для Интеловских машин. Кое-кто из наших читателей уже совершил первую попытку установки. Успешно. Одна беда - нет никакой связи с существующими ОС - не понимает на FAT :-(. Но, по идее, должна бы понять со временем - авторы обещали.