«Материалы Всероссийской научно-технической конференции «ИММОД-2003».23-24 октября 2003, стр.89-10. Syrjakow M., Syrjakow E., Szczerbicka H. Towards a Component-Oriented Design of Modeling and Simulation Tools// Proceedings of the International Conference on AI, Simulation and Planning in High Autonomy Systems (AIS 2002), Lisbon, Portugal, April 7-10, 11. Thomas Wiedemann. Next Generation Simulation Environments Founded on Open Source Software And XML-based Standard Interfaces //Proceedings of the 2002 Winter Simulation Conference (E. Ycesan, C.-H. Chen, J. L. Snowdon, and J. M. Charnes, eds.), pp.623-628.

12. Thorsten S. Daum, Robert G. Sargent, A Web -Ready HiMASS: Facilitating Collaborative, Reusable, And Distributed Modeling And Execution Of Simulation Models With XML//Proceedings of the 2002 Winter Simulation Conference E.

Ycesan, C.-H. Chen, J. L. Snowdon, and J. M. Charnes, eds.,pp. 634-13. Вознесенская Т.В. Математическая модель алгоритмов синхронизации времени для распределённого имитационного моделирования.//В кн. Программные системы и инструменты. Тематический сборник факультета ВМиК МГУ им. Ломоносова №1., стр.56-14. Bagrodia, R., The Maisie Visual Programming Environment, Department of Computer Science, University of California, Los Angeles, http://may.cs.ucla.edu/projects/mvpe/.

15. Миков А.И., Замятина Е.Б. Система имитационного моделирования с XML интерфейсом.// Сб. трудов международной школы-семинара «Современные проблемы механики и прикладной математики», Ч1, т1, Воронеж, 2003, с.244-16. Миков А.И., Замятина Е.Б. Система имитации с удалённым доступом.//В кн. «Материалы третьей междисциплинарной конференции с международным участием (НБИТТ-21), 21-23 июня 2004, Петрозаводск, стр.XII-th International Conference "Knowledge - Dialogue - Solution" 17. Миков А.И., Замятина Е.Б., Осмехин К.А. Метод динамической балансировки процессов имитационного моделирования.//В кн. «Материалы Всероссийской научно-технической конференции «Методы и средства обработки информации МСО-2003».1-3 октября 2005, стр. 472-18. Замятина Е.Б., Муллаханов Р.Х., Фирсов А.Н. On Approach of Researching Portal Development //В кн.

«Информационные технологии и телекоммуникации в образовании и науке», 15-22 May, 2005, Turkey, pp.243-Информация об авторах Александр Миков – директор АНО «Институт компьютинга», Букирева,15, Пермь, Россия, e-mail: Alexander_Mikov@mail.ru Елена Замятина – Пермский государственный университет, Букирева,15, Пермь, Россия, e-mail: e_zamyatina@mail.ru Антон Фирсов – Пермский государственный университет, Букирева,15, Пермь, Россия, e-mail: a_firsov@mail.ru ON RELATIONSHIP BETWEEN A SEARCH ALGORITHM AND A CLASS OF FUNCTIONS ON DISCRETE SPACEVictor Nedel’ko, Svetlana Nedel’ko Abstract: The task of revealing the relationship between a search algorithm and a class of functions those it solves is considered. Particularly, there was found a class of functions solvable by some adaptive search algorithm for a discrete space of low cardinality. To find an optimal algorithm exhaustive search was used.

Algorithm quality criterion based on equivalence classes was also introduced.

Keywords: search algorithm, adaptive search, optimization, global extreme, no free launch theorem.

Introduction According to the no free launch theorem [Wolpert, 1996] a cardinality of the set of discrete functions solvable by a search algorithm is the same for all the algorithms. A function here may be thought as a permutation of integer numbers from 1 to n, and a function is called solvable by an algorithm if the algorithm will find global extreme for given number of steps. This theorem means that having no information about class of functions one can’t prove one algorithm versus other ones.

At the same time the using some comprehensive search algorithm, for example genetic or adaptive one [Lbov, 1965; Lbov, 1999], practically seems to be more reasonable than the random search without any learning. But a rational argumentation of such preference is possible only if functions solvable by chosen comprehensive algorithm occur in real world tasks more often than others. This work presents the results of a numerical experiment that consists in explicit finding the classes of functions solvable by some algorithms including an adaptive search algorithm.

One can introduce on classes of functions a preferability measure that is projected on algorithms. As such a measure a functions class variety may be used. The simplest variety measure is a number of different extremum positions over all functions in the class. The informativity criterion [Lbov, 2001; Nedel’ko, 2004] also may be used as a variety measure.

On algorithms it’s also possible to introduce some complexity measure, for example, as a number of different points arrangements those may by generated by the algorithm over the all functions. For deterministic algorithms this measure corresponds to intuitive measure of “nontriviality”.

The work is supported by RFBR, grant 04-01-00858-a 288 Intelligent Systems The numerical experiment performed reveals a correlation between an algorithm complexity and a functions class variety.

Since a metric is given on definitional domain of functions, the set of all functions may be split onto equivalence subclasses. If one defines that an algorithm solves a given function only if it solves also all the functions of the correspondent equivalence subclass, the number of solvable functions for different algorithms cease to be equal.

Thereby it is possible to introduce some criteria those allow to say that one algorithm is better than another one.

Formal Statement of the Problem The task of global extremum search will be considered in the following statement.

Let unknown numerical function f be defined on a discrete set X ={x j =1,n} and j k j f (x ) f (xk ). Let’s arrange all the values of the function and denote a rank of value f (x ) by f j.

j j Then a function f may be thought as a permutation f j of integer numbers from 1 to n.

A search of extremum (assume that we need a minimum) consists in successive selection of m points from X, i. e. in selection of some subset of indices Jm ={ji In i = 1,m}, where In is a set of integer numbers from 1 to n. When the next point x X is chosen not the true value f (x ), but only ri Ii – a rank of this value ji j among the all previously taken values got to be known.

So a selection of a next point in X may be represented as a function of all the ranks obtained by previous steps, i. e. ji = Qi(r1,...,ri-1). A set of the all such functions for m steps comprises a search algorithm Q ={Qi i =1,m}. Note that for each f an algorithm selects a certain set Jm.

A search algorithm may be represented by a decision tree, where nodes are assigned by ji – indices of selected points and branches correspond to possible values of ranks ri. So the root is assigned by the index of a point selected first. Since for the first point there are no points to compare the only one branch issues from the root.

The second value may be greater or smaller than the first one therefore there are two branches issuing from the second layer node. Similarly, i branches issue from each node of i-th layer.

As a search quality criterion we shall use K(Q, f )= min f – the lowest rank of function values among the ji i=1,m points selected by the algorithm.

We shall say that a function f is solvable by an algorithm Q if K(Q, f )=1, i. e. the minimum was found.

The goal of this paper is to reveal a relationship between an algorithm and a class of functions solvable by it.

Research Method The basic research method in this work is a direct running over all the variants. It poses strong dimensionality restrictions.

The number of all functions is n!, so an exhaustive search over all the functions is possible until n 14.

m The number of nodes in the decision tree for a search algorithm is i!. Since a tree need to be stored i=parameter m should not be greater than 11.

Under these restrictions it is possible to find the class of functions solvable by any given algorithm using exhaustive search over all the functions.

We are interesting also in finding an algorithm being optimal for given class of functions. To solve this task one m n! i! need to store all the combinations of selected ji and received ri. The number of such variants is.

(n-i-1)! i=Therefore the ultimate dimensionality is given by n 12, m 5.

XII-th International Conference "Knowledge - Dialogue - Solution" Permitted for an exhaustive search task complexity is very far from complexities of real practical problems. But it allows modeling quite nontrivial function classes and search algorithms, including an adaptive search algorithm.

No Free Launch Theorem According to NFL theorem an algorithm quality averaged over the all functions is the same for all the algorithms of search. For the considered statement of a search problem it means that the number of functions solved by an m algorithm is the same for all the algorithms. This number is n!.

n This fact means that to prove an advantage of some algorithm one need to have information about functions to be analyzed. Another way is to introduce some characteristics those provide a ranking of classes of functions.

The Equivalence of Functions Until now we didn’t take into account any properties of space X, although such properties are very important for an optimization algorithm.

One of the most important properties is a presence of the metric.

Assume in X the metric (x, x )= ( j1, j2 ) = min( j1 - j2, n - j1 - j2 ) to be given. Note that j1 jthe points x and xn are adjacent. This metric may be illustrated via placing the points on a circle.

The metric introduced allows to define equivalence relationship on functions. Two functions will be equivalent if they may be transformed one to another via some preserving a distance mapping the space X onto itself.

It’s easy to see that functions f (x) and f (x) are equivalent if and only if the correspondent permutations f and f may be transformed one to another via a round permutation and a mirror reflection if needed.

j j We shall say that an algorithm solves a function if all the functions of correspondent equivalence class are solvable by this algorithm.

Note that while the number of functions solvable by any algorithm is the same, the number of solvable equivalence classes may be different, so it may be used as a measure of effectiveness.

Adaptive Search Algorithm Placing five points in a space of cardinality 10 one can only approximately model an adaptive search, but the basic ideas of this algorithm may be represented. The main idea of adaptive search is an inclination of the next selected point both to less investigated areas of X and to already known points with smallest f (x).

But this idea may be realized by various ways, so to avoid ambiguity let’s use a class of functions. It’s clear that functions solved by adaptive search algorithm should satisfy the condition of that the function values in close points are usually close. Let’s take a class F of functions with restricted variation speed, i. e. f F f - f ( j1, j2 ). Let = 2 that is the lowest possible value. Note that if f F then the all j1 jequivalent functions also belong to F.

The content of F2 by m = 4, n = 10 is shown in table 1 where only one function from each equivalence class is presented.

Under m = 4, n = 10 the class F2 is solved by the algorithm that represented on figure 1 via a decision tree.

Note that this algorithm completely reflects the ideas of adaptive planning. Indeed, the first three points are arranged equidistantly: on the first step the algorithm selects the point number 1, on the second step — the point number 4, on the third step — the point number 7 if f4 < f1 and the point number 8 else. On the fourth step the algorithm selects a point near to previous points where smaller function values encountered, for example if f7 < f4 < f1 then the algorithm selects the point number 6, if f4 < f7 < f1 — the point number 5 etc.

Besides introduced in tab. 1 functions the algorithm solves 955 equivalence classes more. Some elements of these classes are in table 2.

290 Intelligent Systems The results obtained show that an adaptive algorithm can solve some equivalence classes including functions with rather quick changing. But in all solved classes the functions have minimum and maximum on the far distance.

7 6 5 3 9 10 Fig. 1. The decision tree for the algorithm being optimized on the class Fby m = 4, n = 10.

Tab. 2. Some extra classes of functions solved Tab. 1. The class Fby the algorithm being optimized on the class F7 5 3 1 0 2 4 6 8 4 5 7 2 0 6 3 1 9 7 5 4 1 0 2 3 6 8 5 1 7 3 0 6 4 2 8 7 6 3 1 0 2 4 5 8 4 6 7 2 0 5 3 1 9 7 6 4 1 0 2 3 5 8 5 6 7 2 0 4 3 1 9 8 5 3 1 0 2 4 6 7 6 2 7 1 0 5 3 4 8 8 5 4 1 0 2 3 6 7 9 2 5 3 0 4 7 1 6 8 6 3 1 0 2 4 5 7 8 1 6 3 0 5 4 2 7 8 6 4 1 0 2 3 5 7 Conclusion The research performed demonstrates that the method of a direct running over all the variants is appropriate for revealing some properties of search algorithms and a relationship between an algorithm and a class of functions solvable by it. The method allows explicit finding an algorithm being optimal for given class of functions. Note that the analytic finding an optimal algorithm is very difficult because an algorithm selecting on a regular step a point with maximal probability of extremum is not generally an optimal algorithm, so one need while planning a regular point to take account of the following steps.

Using this method we have found out the adaptive search algorithm to be optimal for the class of functions with the lowest changing speed.

The using a number of metrical equivalence classes solved by an algorithm as an effectiveness measure was also suggested.

XII-th International Conference "Knowledge - Dialogue - Solution" Bibliography [Wolpert, 1996] D. H. Wolpert, W. G. Macready. No Free Lunch Theorems for Search. Santa Fe Institute repot, SFI-TR-95-02-010, 1996.

[Lbov, 1965] G. S. Lbov. The choice of effective system of interdependent features. // Computational systems, N 19, Novosibirsk, IM SB RAS, 1965, pp. 21–34 (in Russian).

[Lbov, 1999] G. S. Lbov, N. G. Startseva. Logical decision functions and issues of statistical robustness. Novosibirsk, IM SB RAS, 1999, 211 p. (in Russian).

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.