Эволюция графа

Почему именно эволюция? На это есть веские основания. Дело в том, что при изменении сложной структуры зачастую неизвестно, как скажется на работе объекта то или иное изменение. Если бы это было известно, то не было бы проблемы структурной адаптации.

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

Эволюция графа не может происходить без его случайного изменения. Эти случайные изменения и порождают его «потомков». Например, можно произвольно ввести новое ребро в граф, выбросить случайно выбранное, перекинуть конец какого-то ребра на любую вершину или каким другим образом случайно изменить граф. Полученный «потомок» следует оценить по критерию эффективности. Если он оказался хуже, то следует снова произвольно изменить исходный граф и получить нового случайного «потомка». А если «потомок» оказался лучше своего «родителя», то ему и «продолжать» род: именно он теперь будет случайно изменяться до тех пор, пока не даст «потомка» еще лучшего. Повторяя этот процесс эволюции достаточное число раз, можно быть уверенным, что в конце концов мы придем к искомому графу. Залогом тому является случайность мутаций графа, которая гарантирует нам реализацию всех возможных структур графа, среди которых имеется искомая — ей просто некуда деться!

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

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

Таким образом, адаптация графа путем моделирования его эволюции со случайными мутациями и отбором всегда позволяет получать структуры объектов с высокими показателями эффективности. Успешность этой процедуры гарантируется тем, что используются случайные мутации графа. Именно случайность обеспечивает работоспособность такой структурной адаптации!

  • Хотите подключится к интернету в Киеве но не знаете какой провайдер выбрать?, тогда на сайте http://www.lanet.ua/ собрано большая база провайдеров с описаниями и характеристиками. Лучшие провайдеры ждут Вас.