: The synchronization task. The problem of arrows (in technology). Calculation task Game "Life" (Conway). Properties of the airframe. Possible variations. Evolutionary programming (genetic algorithms).

Synchronization task

The problem of arrows (in technology)

This procedure can be built on a three-state automaton S ₀ , S ₁ , S. S ₀ is the initial state.

When a signal arrives, the automaton goes to state S ₁ . If the signal arrives when the machine is in the S ₁ state, and neighbors in the S ₁ state are next to it, then it switches to the S state.

There are synchronous and asynchronous machines. In asynchronous no simultaneous signal arrival is required.

The rules of the asynchronous machine for solving this problem
1) S _i ^t = 0 AND S _j ^t = 0 -> S _i ^{t + 1} = 0; S _j ^{t + 1} = 0
2) V = 1 S ^t = 0 -> S _i ^{t + 1} = 1;
3) S _i ^t <> 0 OR S _j ^t <> 0 -> S _i ^{t + 1} = min (S _i ^{t + 1} , S _j ^{t + 1} ) +1; S _i ^{t + 1} = min (S _i ^{t + 1} , S _j ^{t + 1} ) +1;

Automata can be made to solve the problem (synchronize) in less time. This requires an increase in the number of states of the automaton.

An example of a self-synchronizing system is a laser that is out of sync - the transport stream.

The most acute problem of synchronization is in air defense systems and chip design.

Calculation task

Multiplication of binary numbers consists of two operations - shift and addition. An automaton, each cell of which can have 27 states in 15 cycles multiplies two four-digit numbers. n is the number of digits. 3 * (2n + 1) - the amount of state. (8n +2) - the number of cycles. Read more

NP-complete tasks require iteration of all data (everything should be compared with everything). The complexity of these tasks grows exponentially depending on the number of elements. But on pasta machines are solved instantly - the solution is determined linearly. Read more

Game "Life" (Conway)

Conway investigated the interval (2; 3). There are stable combinations that do not change over time, such as, block and hive. Stable dynamic combinations (semaphore). The world clock (absolute metronome) determines the speed of light (C) in this system - they decrease at one end by one square per beat. Glider - analogue transmission of a bit of information; it turns into itself after 4 clock cycles shifted in space by one cell (the transmission speed of a bit of information - C / 4).

Illustrations ...

Airframe properties:

On such a homogeneous structure, one can imitate information structures, imitate information processes occurring in them, build a computer in which there is no processor as such, or distinct places where certain functions are performed.

Possible variations

Thus, the automaton is described as four parameters - (D, R, S, M). (1D, 1R, 2S, 1M) - the easiest, the game takes place on the line. (2D, 1R, 2S, 1M) implements Conway's Life. Automata were found that can be used in cryptography, in the process of restoring the destroyed image, in geographic information systems. They are also successfully used to generate images and music (3D, 2R, 256S, 3M); modeling processes in chemistry, biology, economics.Read more

Evolutionary Programming (Genetic Algorithms)

Examples

Breakwater design in Novorossiysk. It was required to construct a breakwater. The usual means to do this for a long time failed. Then it was used evolutionary programming. Geometric parameters of the breakwater were used as the genome. An environment model was created on which the resulting variations were tested.

Generate realistic images. Description can be found in the articles:
"Computer models the evolution of plants",
"Programs that simulate the evolution of Paleozoic biological species and the evolution of English surnames",
"Programming and art."

Layout rocket flow. There are three components. It is required to put them together for maximum volume and maximum streamlining. Using evolutionary programming, the following result was obtained.

Geometric modeling.

Gathering a combination of elementary functions D1-D8, you can design a variety of different geometric regions. For example, the FORMULA for a picture of a complex area might be: D1 * (1-D2) + D3 * D4 * D7 + D8 * D6 * D4 * (1-D5) or similar. Variations may undergo in the formula signs, brackets, indexes. Will get all the new shapes.

It is required to carefully study the parameters of the genome. It should be as general as possible. You need to vary the parameters continuously.

On this idea, developed a method called Artificial life.

Artificial life is a generalized method for constructing dynamic models based on a combination of genetic algorithms, chaos theory, and system dynamics.
Features of the method:
-adaptation of the solution to the conditions of the outside world,
- transfer of traits by inheritance,
-mutation,
-immit survival.

The concepts of the method.
Chromosome - vector of variable decision parameters
Operations - getting new solutions from existing
Crossing - getting chromosome parameters from parents, expanding the search area
Mutation - random change of parameters when copying
The reaction of the world - the destruction of the percentage of the worst individuals (according to the criterion of the environment), the narrowing of the search area

To solve the problem (for example, the synthesis of the ideal form of a fighter) it is necessary to build an environment, a multitude of objects, to imitate their interaction, crossing and death. In the change of generations, the process of evolution and the transition to the ideal. It is argued that this method is amenable to problems that have many parameters, undetermined by many factors, with steep fronts in the objective functions. That is, those that can not handle the theory of system analysis and optimization

A. Masalovich "By the path of the Creator or the first steps of" artificial life "

PC WEEK / RE October 8, 1996

This wave swept the scientific world so suddenly that it caught both potential supporters and opponents off guard. The unusual name - “Artificial life” (artificial life, like this - no more, no less!) Did not have time to gain a foothold, as in Spain a large international congress ECAL took place, entirely devoted to the problems of new science, and the researchers announced the coming of the fourth wave of artificial intelligence . What is this mysterious science, familiarity with which causes love at first sight or instantly incredulous rejection, but always - astonishment on the verge of philistine resentment: "It turns out there, around the corner, already walking with might and main, and here we miss with an empty glass!".

Artificial life - a new word on the letter A

The fate of new scientific trends - with all their revolutionism, singularity, and paradoxicality - usually develops according to the canons of classical melodrama, repeated the eternal tale of Cinderella. Recall: to the poor Cinderella, sorting through a bag of lentils (the symbol of the draft scientific work of a generation of nameless devotees) is the Good Fairy (a large customer, usually military or financier) and sends her in a fabulous outfit to the ball in the shining palace (gives a serious order and solid funding ). But alas, the clock strikes midnight, the golden carriage turns into a pumpkin, and poor Cinderella goes to the backyard of science for a long time, to the immense joy of the envious sisters. It usually takes many, many years to make sure that the glass slipper of a new applied task is just one mysterious fugitive, and the matured Cinderella returns to the palace with triumph — now as a queen.

This simple plot is traced in the development of almost all new sciences - the theory of neural networks, and fuzzy logic, and genetic algorithms, and system dynamics, and others. All but one. In the case of Artificial life (or A-life, as familiar American journalists christened the new science), neither the good fairy, the insistent prince, nor the services of fabulous fashion designers were needed. Cinderella hit the ball straight from the kitchen - in a patched apron and holding a ladle in her hands. However, it is long past midnight, and the stream of flattering and tempting offers from the most distinguished fans does not dry out ...

So what is Artificial life? The most general definition is provided by the magazine MID RANGE Systems, interpreting A-life as “computer modeling of living objects” (MIDRANGE Systems, 1995, v. 8, No. 13, p. 29). However, in practice, computer models with a number of specific features are usually attributed to A-life. First, the central model of the system — whether it’s a child’s character, a self-propelled robot, or an intelligent Internet agent — has the ability to adapt to the conditions of the outside world, adding to the knowledge about it by interacting with other objects and environments. Secondly, the components of the system, developing in the process of evolution, are able to pass on their characteristics by inheritance, that is, there is a mechanism for generating new generations — by dividing, crossing or duplicating existing objects. Thirdly, the world around is tough enough and minimizes the chances of survival and the emergence of offspring in weak and ill-adapted individuals. And finally, there is a mechanism for generating new forms (an analogue of mutations in the real world), usually containing an element of chance.

In other words, to solve the real problem with Artificial life methods (for example, to create a fighter of ideal form, or to develop an optimal strategy for an exchange game, etc.), it is necessary to build a dynamic model of the environment in which the projected object is to exist, to populate it with many varieties of this object and give them a few generations to live. Weak individuals will die, strong ones will interbreed, securing their best traits in new generations. After a few dozen (sometimes hundreds and even thousands) cycles, such a selection will generate a “civilization” of practically invulnerable individuals, ideally adapted to the model of the world you specified. It’s not a fact that the result will correspond to your ideas of the beautiful (and in general will be close to the expected). But it can be said with confidence that the "life force" of the past most severe selection of the solution will be sufficient to successfully counter any actions of competitors.

What caused the birth of a new science? Why it is impossible to solve the same problems with the classical methods of control theory, optimization and system analysis? The fact is that any designer of complex systems faces the same set of problems that are difficult to solve by traditional methods. The incompleteness of knowledge about the outside world, the inevitable error of sensors, the unpredictability of real situations - all this makes developers dream of adaptive intelligent systems that can adapt to changing the rules of the game and independently navigate in difficult conditions.

The "curse of dimension" becomes a real deterrent to solving many (if not most) serious tasks. The designer is not able to take into account and reduce to the general system of equations the entire set of external conditions - especially if there are many active opponents. Independent adaptation of the system in the process of dynamic modeling of “conditions close to combat” is perhaps the only way to solve problems in such cases.

There is one more reason - philosophical. Have you ever noticed that all attempts of purposeful selection and improvement made by a person doom the object of selection to degeneration? Thousands of examples. Remember the fate of the royal families of the Middle Ages, compare the elite breeds of dogs with cheerful mongrels, finally, try to plant your favorite cucumbers outside the greenhouse! One gets the impression that a person is so far deprived of the ability to predict the long-term consequences of his own, even if caused by the most good intentions, actions. So let us put down pride and return the functions of the Creator to Mother Nature. Let the vitality of decisions be verified by life itself.

"Is there any science here at all?" - will ask a picky graduate of mekhmat. Right. Strictly speaking, Artificial life is not a science, but rather a generalizing method for constructing dynamic models based on a set of other sciences - genetic algorithms, chaos theory, system dynamics, etc. Each of them is worth a separate conversation (and PC WEEK / RE must will return to them. - Ed.), for now let's briefly get acquainted with one of the main whales on whom Artificial life relies. This is the mathematical apparatus of so-called evolutionary computing, better known as "genetic algorithms."

Genetic algorithms

From a mathematical point of view, genetic algorithms (GA) are a kind of optimization methods that combine the features of probabilistic and deterministic optimization algorithms. The search for the optimal solution with the help of GA begins with the representation of the parameters of the solution in the form of a vector (integer or bitwise) - the “genetic code” or “chromosome”. Next, a set of operations is determined, allowing to obtain new solutions from the set of existing ones. Continuing the analogy with the genetic mechanisms of the real world, the “subsidiary” decision can be generated by one or two “parents”, inheriting the traits of both as a result of crossing operations. However (and this is perhaps the most important) new generations copy the properties of their predecessors inaccurately. There is a special mutation mechanism that introduces random distortion. Finally, the model of the external world in the implementation of genetic algorithms is usually, alas, absent, which distinguishes GA from Artificial life as a whole. The reaction of the external world is replaced by a predetermined target function, which allows to compare the quality of the solutions obtained.

Then everything is simple. On the basis of one or two initial decisions, the first generation of subsequent decisions is generated. For each, the value of the quality function is calculated, after which a certain percentage of the worst solutions are destroyed and the best ones are crossed. So the next generation appears. Mutations periodically expand the base for selection, not allowing the process to degenerate. After several generations, the value of the quality function ceases to grow. This means that a family of solutions that best satisfy the specified criteria is derived. It remains only to "decipher" the genetic code of the final decisions and translate them into the usual form for the developer.

This is how most of today's programs that implement genetic algorithms we work. Так (или примерно так) выглядит базовая идея GA, изложенная в классической книге основоположника генетических алгоритмов Джона Холланда (Holland JH Adaptation in Natural and Artificial Systems. The University of Michigan, 1975). Однако понадобилось двадцать лет, чтобы идея была соответствующим образом исследована и воплощена в коммерческие изделия для массового рынка. Причина - в трудноформализуемости базовых концепций GA.

To be honest, the author of this article originally treated genetic algorithms with some distrust. I was confused by the paucity of fundamental results (with the exception of two theorems), as well as the deliberate lack of guarantees of convergence. For any class of problems and any type of GA, it was possible to build an example where GA is inferior in speed of convergence to classical algorithms or it works for an infinitely long time. To fully appreciate the power and beauty of genetic algorithms was only possible thanks to one occasionally seen impressive example.

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

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

Некоторые практические приложения GA будут приведены ниже. Те же, кого заинтересовал именно данный пример, могут найти описание ряда подобных экспериментов, например в статье (Plain SW Simulated wetware. Computer Shopper, 1995, v. 17, № 7, р. 584).

A-LIFE в бизнесе: полет нормальный

Если вернуться к истории с Золушкой, то в случае с A-life изумляет полное отсутствие злой мачехи. У новой науки практически нет явных противников. Более того, многие представители большого бизнеса (в том числе такие гиганты, как Ford) заявляют, что уже давно используют элементы A-life в ситуационном моделировании и деловых играх для руководителей. Автору статьи доводилось принимать участие в одной такой игре, организованной лос-анджелесским университетом. Здесь место теплого океана из приведенного выше примера занял безбрежный рынок США , населенный сонмом акул-конкурентов, а место несчасной биомассы - фирмы, отданные в управление каждому из участников. За один такт игры надо было оценить позиции своей фирмы на различных рынках нескольких городов, закрыть убыточные филиалы, реорганизовать неэффективные и расширить прибыльные, т. е. принять в общей сложности около пятидесяти управленческих решений. Через полчаса центральный компьютер подводил общие итоги такта (равного кварталу работы фирмы) и переходил к следующему "поколению". Вот только все функции оптимизации, скрещивания и т. д. приходилось делать вручную (поскольку основная идея GA - обеспечить выживание популяции, а в реальном бизнесе вас больше волнует судьба конкретной особи). Интересно, что к концу вторых суток игры практически все российские участники (около двадцати) не только закрепились на рынках всех игровых регионов, но и начали постепенно теснить "хозяев поля". Эволюция превратила аморфную биомассу в акул.

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

Разработчики БИС всерьез увлечены созданием нового поколения микросхем, реализующих базовые алгоритмы A-life "в кремнии". Пионером здесь выступает легендарный профессор Mead (пятнадцать лет назад создавший первый "кремниевый компилятор" - полностью автоматическую САПР заказных БИС). Он разработал асинхронный нейроноподобный кристалл, на котором собирается для начала реализовать модели глаза и уха, и уже получил первый патент на однотранзисторную модель синапса. А на конференции ECAL была продемонстрирована первая программируемая микросхема (ПЛМ), способная к самосовершенствованию. В схему "зашит" генетический алгоритм, оптимизирующий программный код обработки внешних воздействий.

Businessmen are well acquainted with Flavors Technology, which solves many hard-to-formulate financial and managerial tasks using A-life methods and chaos theories implemented on a specialized multiprocessor system. It is less known that the firm Thinking Machines, the famous developer of supercomputers, also has its own software developments on the implementation of A-life to solve a number of defense tasks.

Such an exotic area as computer virology stands apart. Researchers using the A-life methods approached this problem by treating computer viruses as a specific kind of artificial life capable of mutations, reproduction, habitat infection and self-improvement. With this interpretation, the long-standing idea of ​​a universal antivirus that will detect not specific types of viruses (like most existing programs), but manifestations of computer life forms — changing the interrupt handling discipline, atypical behavior of well-known programs, unfamiliar “handwriting” of program communication with the file system — becomes a reality. system, etc. IBM has already announced the first commercial antivirus built on similar principles.

As for such areas as modeling of catastrophes, emergency situations and military conflicts, here the history of situational centers, actually using elements of A-life, has been around for several decades. Numerous examples of such applications can be found on the NASA Technology CD-ROM, from which the security classification was recently removed. It is curious that immediately after this a disk (still not authorized for export from the USA) appeared on the market in Moscow.

And in that order there is a small gap ...

An arbitrarily beautiful and interesting theory takes possession of the masses only when simple and convenient tools come into the market, making experiments with new concepts publicly available. Fortunately, such a tool already exists for A-life, moreover, it is also in Moscow.

The main component of A-life systems are packages that implement genetic algorithms. The most common are two such packages: Evolver (the first of the massive GA packages, recognizable by the characteristic picture with apes on the cover), and the later and powerful Gene-Hunter package from the Ward Systems Group. The latter is especially popular because it is part of the Ward neural network package, which is actively used by Russian bankers for a portfolio game and currency dealing.

For those who think that new technologies are something infinitely far from the everyday problems of real business, we offer a little experiment. Imagine that you are the owner of a small company engaged in screwdriver assembly of computers. You have several varieties of each component of a PC in your warehouse — drives, housings, motherboards, etc. I’m not going to explain to me that the price of the assembled computer is not equal to the sum of the prices of its components. An elementary optimization problem arises - how to assemble computers from all this stuff in order to get the maximum profit? I am ready to say that even with a microscopic turnover of 100 million rubles a month, it is almost impossible to get the optimal solution "manually". And the GeneHunter package will cope with this task in a few minutes, and solving only this one task will pay for its cost in a week. By the way, some far-sighted dealers have already realized that all of the above is true not only for computers, but also for increasing the profitability from the sale of furniture, building materials, as well as a host of other applications.

To build real economic and political models, packets based on fuzzy logic are also used. The most famous package is CubiCalc, which allows building expert systems with fuzzy rules. He is loved by bankers and economists, inspired by reports about the successful use of such systems by Japanese financiers. Thus, it is reported that Fuji-bank, using a similar modeling system, increased the profitability of short-term dealing operations by $ 700,000 per month.

In tasks of situational modeling, the most widely used is the iThink package, which implements the methods of the so-called “system dynamics”. Its main consumers are also financiers and large government agencies. The former are concerned with the issues of modeling various financial markets and optimizing the activities of financial-industrial groups, while the latter are more concerned with macroeconomic and political models. By the way, with the help of iThink, the model of assessing the political preferences of the electorate was implemented, which was on “combat duty” in one of the top-level government structures until the successful end of the presidential election.

As for truly mass products designed for "poor students", here we sincerely advise you to start with a book (Clarkson, Mark. Creating Artificial life with Visual C ++. Windows Hothouse, 1995), containing everything you need to build your own "artificial worlds". In independent experiments with genetic algorithms, article J, Kohn (ConaJ. Developing a genetic programming system, Al Expert, 1995, v. 10, No. 2, p. 20) will be of great assistance. In the wilds of the Internet you can find several servers specializing in Artificial life and genetic algorithms. In addition, on the Toshiba WWW-server, you can get the alpha-version of the Enfant package - a C ++ class library that allows you to build any kind of neural networks, cognitive fuzzy systems, and arbitrary control models. However, the Enfant project also deserves a separate discussion ...

Financiers recommend a recently published book (Bauer RJ. Genetic Algorithms and Investment Strategies.John Wiley & Sons, 1995) - almost the first clearly explaining practical ways to actually increase profits from financial operations using genetic algorithms.

There are also A-life implementations for the youngest computer lovers. These games are truly an ideal ground for running in and popularizing new technologies. We especially recommend you to pay attention to the Anap Galapagos game. It would be an unremarkable "walker", like thousands of others, if not for one circumstance. The protagonist of the game, a dull creature named Mendel, has the ability to learn and gains experience by watching your attempts to get him out of Galapagos. So do not be surprised if, after the third swim in the hot lava, he will no longer obey your commands and approach the dangerous areas.

The games that use the elements of A-life, also specializes the company Maxis. So in the new strategic game Mission in the Rainforest you are given 10,000 square miles of forest area in Malaysia, and your task is to turn the region into an “ecological paradise”. And in the best-selling game Unnatural Selection, you have an A-life lab at your disposal to launch a creature named Theroid, able to curb the host of monsters generated by the sick fantasy of an insane professor of genetics.

And for those who prefer serious scientific work to games, the most systematic information on the A-life problem is contained in the proceedings of the ECAL-95 conference (Granada, Spain, June 1995).