Modeling and computing methods for solving optimization problems.

Hrubina, K. ; Katalinic, B. ; Jadlovska, A. 等

1. Introduction

The aim of the paper is to present the designing of mathematical and computer models of the defined problem based on isomorphism and homomorphous representation, a theoretical basis of genetic algorithms, their essence and a principle as well as the possibilities of their application to the solution of selected optimization problems. Models of operational research are systems which are a simplified image of objective reality. They are of a mathematical character, i.e. they contain equations, inequalities, differential equations and differential-difference equations. Such modeling method belongs to mathematical modeling; mathematical models themselves, considering the form of uncertain variables occurrence, can belong to some of the following categories of models: deterministic, stochastic, strategic, adaptive and fuzzy. A criterion function an objective function with these models represents the extent of the evaluation of the achieved goal which was defined for the given system. The solution to the defined problem represented by a model often consists in finding an extreme of the criterion function, i.e. the point, eventually n-components of a vector in which the function attains its maximum or minimum. Such a vector represents the best variant of the problem under solution of the given set of variants. In this sense we speak about optimization and optimization methods. Thus, optimization in informatics means searching for "the best solution to the defined problem". In case of incomplete information about a composite system, eventually a regulated process, this refers to the system with incomplete information, therefore the methods of a new scientific branch--artificial intelligence--have to be used. The methods and the means of artificial intelligence include

* Solution methods for problems with constraints.

* Genetic algorithms.

* Neural networks theory.

* Expert systems.

* Methods of chaos theory.

Nowadays, based on Darwin's theory of evolution, evolutionary algorithms are being developed very fast. They are the essential instrument of informatics and modern numerical mathematics applied to the solution of complex optimization problems. (Eiben & Smith, 2003, Hrubina & Jadlovska, 2002)

2. Processes modeling

The basic notion of the theory of modeling and modeling in general is a model. There are many definitions of a model that are often set out intentionally in order to emphasize the characteristics which would be investigated and compared based on the defined models. In this connection, it is necessary to introduce some other notions as well. An object (process, phenomenon, etc.) will refer to a purposely specified part of objective reality which is the subject of our further investigation or utilization. An object, however, is approached to in a much more general way and it also includes a system, a real system, a notion. It means that, in a broader sense, this refers to a defined reality, sometimes even of an abstract content.

2.1 Isomorphism and homomorphism

A model is an isomorphism or homomorphism representation of an object in the form of a selected objective set transferring object characteristics adequately to a representation.

[FIGURE 1 OMITTED]

Representation. Let us have two un-empty sets A and B whose elements can be arbitrary objects. The representation f of the set A to the set B is such a rule according to which each element x[member of] A is assigned one defined element y [member of] B. The element y assigned to the element x by the representation f /Fig.1. is denoted

y = f(x) or f: A [right arrow] B or f(A) [subset or equal to] B (1)

Frequently, the expression operator is used instead of the representation, although the notion operator is commonly referred to more complex representations, especially the functional ones. The representation f of the set A to the set B is called an injective representation if

([for all]([x.sub.1] [not equal to] [x.sub.2]), [x.sub.1], [x.sub.2] [member of] A) [right arrow] [right arrow] (f ([x.sub.1] [not equal to] f ([x.sub.2])) [member of] B) (2)

When the representation f is injective, there exists to it an inverse representation [f.sup.-l] such that it holds

([for all]x [member of] A|y = f (x)) [right arrow] [f.sup.-1] ((y) = x)

Let A, B be the subsets of real numbers. Let the representation f be such that each x [member of] A is assigned its square. This representation is the function y= f (x)= [x.sub.2]. It refers to a non-injective /Fig. 3 a). The notions isomorphism and homomorphism can be defined with further widening on the systems. Let us have two systems [S.sub.a] and [S.sub.b] which are determined by the triples

[S.sub.a] =[A,[R.sub.a],[F.sub.a]]; [S.sub.b] =[A,[R.sub.b],[F.sub.b]] (3)

Where

A = {[a.sub.1] ,[a.sub.2],...,[a.sub.r] };A = {[b.sub.1] ,[b.sub.2],...,[b.sub.s]} (4)

are the sets of elements of individual systems [S.sub.a], [S.sub.b]

[R.sub.a] = {[r.sub.ij.sup.(a)] = ([a.sub.i],[a.sub.j]) |[for all]i,j([a.sub.i],[a.sub.j] [members of] A)} [R.sub.b] = {[r.sub.ij.sup.(b)] = ([b.sub.i],[b.sub.j]) |[for all]i,j([b.sub.i],[b.sub.j] [members of] B)} (5)

are interrelations between individual elements of the systems Sa, Sb expressing the properties of their elements (subsystems, eventually sub-objects)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

are the functions assigned to the individual elements (subsystems, sub-objects, and the like), eventually to the systems [S.sub.a], [S.sub.b]. We say that the system [S.sub.a] is represented isomorphism to the system [S.sub.b], particularly if for their elements, relations and functions according to (3) - (6) it holds /Fig. 2.

1 [a.sub.i] [left and right arrow][b.sub.i],[for all]i([a.sub.i] [members of]A;[b.sub.i] [members of]B); r = s

2 [r.sub.ij.sup.(a)] [left and right arrow] [r.sub.ij.sup.(b)] ,[for all]i([a.sub.i],[a.sub.j] [members of] A; [b.sub.i],[b.sub.j] [members of] B);r = s (7)

3 [f.sub.ai] [left and right arrow] [f.sub.bi],i = l,2,3,...,[r.sub.a] ; [r.sub.a] = [r.sub.b]

Isomorphism of the systems [S.sub.a], [S.sub.b] will be written such that ([S.sub.a] i [S.sub.b]). From the notion of isomorphism it follows that the following properties are valid

a) commutative

([S.sub.a] i [S.sub.b]) [left and right arrow] ([S.sub.b] i [S.sub.a]) (8)

b) transitivity

([S.sub.a] i [S.sub.b]) [conjunction] ([S.sub.b] i [S.sub.c]) [left and right arrow] ([S.sub.a] i [S.sub.c]) (9)

Isomorphism is realized by an injective representation, which as a result contains an inverse representation as well (thus assuring the commutative of isomorphism systems). At the same time, the transitivity follows from the unequivocal based on the existence of a composite representation. With the isomorphism, the number of elements is preserved and, at the same time, the number of relations and functions is preserved with the corresponding reciprocal pairs. This representation does not lead to a simplification as it only refers to a view of the same object from "the other side".

The homomorphism of the representation only has the property of a transitivity, therefore, for the homomorphous representation it holds

([S.sub.a] h [S.sub.b]) [conjunction] ([S.sub.b] h [S.sub.c]) [left and right arrow] ([S.sub.a] h [S.sub.c]) (10)

The transitivity property is based on the property of existence of a composite representation f(g(x)).

[FIGURE 2 OMITTED]

Based on the introduced notion of a model, models are classified according to a performed representation as follows

a) Isomorphism models,

b) Homomorphism models.

Isomorphism models are complex objects, similarly as original ones, for example, two vehicles of the same series are the objects that can mutually be represented isomorphism.

[FIGURE 3 OMITTED]

Similarly, a true reduced replication of the mentioned vehicle represents its isomorphism model. For instance, in the sets of real numbers, an isomorphism representation of the real axis [o.sub.x] is the function y = 3[x.sup.3] - 1000. The advantage of isomorphism objects is that they preserve the number of elements between an object and a model, the number of considered relations and functions on them. We say that a model truly represents an object and we actually can replace the object by the isomorphism model. They are utilized, for example, with space flights, a ship repairing is simulated on the Earth and the repairing procedure is then delivered to the ship. Disadvantages of isomorphism models are (primarily from a standpoint of their investigation) a complexity regarding the number of elements, relations, and realized functions on the object which are transferred to the model. When investigating and learning the object, it very often needs to be simplified and released from unimportant processes and actions connected with it. A homomorphous model is for instance: The equation of a deflection curve y = f(x) of a simple beam E.[Jy.sup.(4)] = q(x) where E is a module of a beam cross section elasticity, J--a module of a beam cross section inertia, x--a distance from the beam origination, q(x)--a given loading either continuous or discontinuous, represents a model of a simple beam operation with the application of the q(x) loading, (Hrubina & Jadlovska, 2002).

3. Mathematical and computer model

3.1 Mathematical model

Mathematical modeling includes three mutually dependent stages

1) Formalization of the process under investigation--a mathematical model generating.

2) Designing of an algorithm and a computer programmed for the calculation of numerical values of parameters that are being determined.

3) Assessment of a conformity between a model and an investigated process.

When assessing a mathematical model, a real phenomenon is simplified, schematized and the scheme obtained is expressed in dependence on the phenomenon complexity by means of a selected mathematical apparatus.

A model has to reflect all most important factors affecting the process it has to provide a sufficiently true description of both quantitative and qualitative properties of the process that is being modeled.

A mathematical description of the model structure according to the character of the process is a system of linear, non linear, differential or difference equations which reflect a mutual influence of different parameters. In the mathematical description of the equation of one type they do not exclude the occurrence of equations of another type. Mathematical modeling is not in contradiction to physical modeling it is rather its replenishment. Physical modeling is not determined to analyze specific properties of a mathematical description it is used to assess the objects adequacy based on the comparison of the values of some determining complexes in mathematical equations. With mathematical modeling, the process is under investigation. Accordingly, various parameters of a mathematical model that is modeled on a computer are changed. This enables to obtain information about various variants of the investigated process very fast. Within a reasonable time it is possible to realize optimum variants of a model which means to carry out a mathematical model optimization. Mathematical modeling is much cheaper than physical modeling regardless it expresses money costs or time costs.

3.2 Computer model

The process of computer modeling includes

* system identification

* system simulation.

The principal stages of computer modeling are presented in /Fig. 4. A computer model is a technical realization of mathematical modeling of the followed object (process) on a computer. A computer realization is based on a mathematical theory of the problem because the work with the computer model has characteristics of a classical experiment. The main attribute of the method is the real phenomena simulation by the computer model, therefore we speak about simulation. Simulation is the process which includes

* A computer model generation

* Experiments with the model

* Application of simulation experiments results to the followed object.

[FIGURE 4 OMITTED]

4. Theoretical basics of genetic algorithms

Darwin's theory of evolution contains the following three components

1) Natural selection--there is more probability that individuals having better abilities to survive in the environment they live in are capable of reproducing themselves than less fit individuals. The potential of an individual for survival in the environment is called fitness.

2) Random genetic drift--this refers to random events in the life of individuals. For example, a gene mutation of a random gene, or a random death of an individual with a high fitness level.

3) Reproduction process--by a quasi random selection and crossing over, offspring is produced.

4.1 Representatives of evolutionary computational techniques (ECT)

Evolutionary algorithms based on the metaphor of Darwin's theory of evolution represent a new untraditional approach to searching for an optimum (or suboptimum) solution of complex optimization problems that cannot be solved by classical techniques.

The representatives of evolutionary computational techniques (ECT) are:

* evolutionary strategies (ESs)

* evolutionary programming (EP)

* genetic algorithms (GAs)

* genetic programming (GP)

* differential evolution (DE)

* artificial immune system (AIS)

* Others (artificial life,...)

Evolutionary strategies (ESs)

Evolutionary strategies rank among historically first evolutionary computational techniques. Nowadays, ESs are very well developed stochastic optimization methods, but they still remain connected especially with technical applications to the fields of engineering.

Evolutionary programming (EP)

Evolutionary programming (EP) is the strategy similar to a GA. However, it emphasizes a linkage between a parental and offspring behaviors instead of searching for analogies of genetic operators from nature. EP, likewise GAs and ESs, is a useful optimization method in such cases where searching by means of a gradient fails.

Genetic algorithms (GAs)

Genetic algorithms are a universal stochastic search method which within a bounded domain of permissible solutions to the given problem is capable of approaching a global optimum. The principle observed in nature relating to the survival of the strongest individuals and the inevitable extinction of the weakest ones is applied. The evaluation of such individuals' ability is performed based on a suitable cost function, which actually represents the core of the optimized problem. The models of the basic genetic operations, such as crossing over, mutation and selection, are applied to the calculations.

Genetic programming (GP)

Genetic programming (GP) is a widening of a genetic model of learning into the sphere of programmed. It means that the individuals who form a population are not strings of characteristics with a fixed length, but they are the programmed which, after being run, are possible solutions to the given problem. These programmed are expressed by means of analytical trees instead of source codes. Programmed in a population consist of elements of two series: function and terminating. A certain number of symbols as a suitable solution to the given problem is usually chosen of them. A genetic operator, crossover, is implemented as an exchange of selected subtrees based on the extent of a suitability. GP does not use a mutation operator.

Artificial immune system (AiS)

Similarly to other methods of ECT, the approach which simulates the principle of an immune system in living organisms was also inspired by nature. Therefore, its name is artificial immune system. Algorithm of AIS combines a local as well as global search. Compared to a common GA, ES or DE, this algorithm requires that a fitness evaluation in each generation is provided several times. Besides a complete algorithm of AIS, it can be beneficial to utilize only some parts of it in order to improve another type of evolutionary algorithm.

Artificial life (AL)

This primarily refers to the simulation of individuals or groups manifestations of life. Artificial life penetrates into various fields, not only biology and informatics, but also into physics, sociology, psychology, ecology and philosophy. Christopher Langton, the founder of artificial life, defines artificial life as a study of artificial systems which behave in a similar way as natural living systems. It is an effort to explain the phenomenon of life in any form regardless of the systems which were developed on Earth. With most examples of artificial life, the populations of data structures do not represent any living organism or a process, but they are rather subordinated to artificially created laws which are derived from the laws valid for living organisms.

4.2 The essence of genetic algorithms

The basic objects in a GA are a string, gene and population. The basic operations which are related to these objects are crossover, mutation and selection.

String (chromosome) is a sequence of numerical or symbol values representing selected properties or parameters of an individual (a phenotype) of a problem domain (a domain of real physical objects). Strings can be represented by means of binary values, integers, real numbers values, symbol values as well as their combinations. The method of the used encoding depends on the character of the problem being solved.

Gene is a construction unit of a string. The notion of gene can be explained as parts of strings which represent elementary characteristics of an individual. Population is a group of a selected number of strings. In a mathematical sense, the population is a two dimensional field, eventually an array of numbers and/or symbols. The population size can either change during a GA solution, or it is constant with most realizations.

Generation is a population in a certain computing stage of a GA solution, eventually its order (also a computing cycle of an algorithm).

Criterion function assigns the value to each string of the population. It represents the core of an optimized problem the task is to find its global extreme. The cost function is the measure of what we want to maximize (capacity, production, gain, etc.) or, on the contrary, to minimize (defects, losses, consumption, and the like). Regarding the calculation, the evaluation of the cost function is often a complicated procedure it sometimes consists of several partial criteria (a multiple criterion problem).

Fitness is a commonly used notion among the terms related to evolutionary calculations (EC) representing the extent of individuals suitability or success. The best fitness in case of a maximization problem is the highest possible value of the cost function, in case of minimization, on the contrary, it is the smallest possible value. Some authors respect a convention that fitness maximizes due to a GA solution. Fitness then stems from the cost function based on a suitable linear transformation and it is proportional to a probability of the given individual survival in a competitive environment.

Mutation is an operation where a randomly selected gene (more genes) of a random string (several strings) in a population changes its value into another random value within a bounded range of values of the space being searched. Mutation enables to find new solutions which have not yet occurred in the population. Mutation is the principal moving force of a GA (EV).

Crossover is an operation where two parental strings are split up in a randomly selected position (or in several positions), but equal for both strings, and they mutually exchange one of two corresponding parts (alternately every other part) of the string. Thus, by crossing over, new different individuals who carry new characteristics of both parents are generated.

Strings selection is a procedure according to which, based on a selected strategy, some strings are selected of the strings of the population in the current generation. The selected strings as well as the strings that are replicated unchanged into the population of a new generation then enter the operations of crossover and mutation.

4.2.1 Selection

Selection is an operation which in a GA simulates the mechanism of a natural selection. Therefore, it should hold that more successful individuals in the population should have a bigger chance to be selected unchanged into a new population, eventually to breed offspring, than less successful individuals. In other words, the probability that a given individual will be selected as a member of a new generation or a parent is connected with his success (his fitness value, eventually the value of his cost function). The selection in a GA can be provided by several methods. The most frequently used methods are as follows:

* Selection by the help of a roulette wheel

* Stochastic uniform selection

* Random selection

* Tournament selection

4.2.2 Selection based on the extent of success

The above mentioned methods are based on a probability model of selection. The following method represents a deterministic method, where the selection is strictly defined by a user. As a rule, it is exactly determined how many replications of individual most successful strings of the population have to be chosen. When using such a selection method, algorithms quickly converge, but mostly only to the nearest local extreme, where they tend to persist for a long time (for many generations). Weaker individuals that are ignored can often contain useful information which can contribute to finding a global extreme. It is suitable to use this method in a GA at least to select the most successful individual from the current population. However, it is recommended to combine it with other selection methods (Mitchell, 1998).

4.3 The principle of a genetic algorithm (GA)

GAs is a universal stochastic search technique or an optimization technique, which, within a bounded domain of permissible solutions to a given problem, is capable of finding or at least approaching a global optimum. At the same time, from nature observed principle of the strongest or most adaptable individual survival and the inevitability of the weakest, unviable, or inadaptable individuals extinction is applied. GAs can be used to solve such problems that can be formulated in the form of optimization problems. This is possible on the assumption that we are able to formulate a criterion function (a cost function) which has to be minimized or maximized. At the same time, for all points of the domain being searched (for all potential solutions) it is possible to compute its value, i.e. evaluate it from a standpoint of a successfulness eventually an extent of a goal fulfillment. A computer representation of the optimized problem a mathematical model as well as a computer simulation are the conditions under which the cost function is evaluated. The principle of problems solution by means of a GA is in a simplified form illustrated /Fig. 5.

[FIGURE 5 OMITTED]

The aim of a GA is to find such a string (a set of elements) which represents the best or at least acceptable characteristics of an object in a beforehand bounded domain of permissible solutions. In general, a GA can be expressed as follows

a) Initialization of the initial population of strings, random as a rule.

b) Successfulness evaluation of all individuals in the population.

c) Random modification of selected individuals from the population (parents).

d) New population formation selecting from original individuals in the population and from offspring produced by a modification of chosen parents.

e) Skip to the point 2 or evolution termination.

After a termination, a resulting solution is the most fit individual from the population of the last generation. In order to solve the defined problems, we will consider a classical structure of a genetic algorithm. During the initialization process, the initial population is generated. If there is not any other possibility, the values of individual genes in the string are generated at random from the defined domain. If there are "sensible" (even though not optimum) solutions available or if we are able to estimate some solutions, eventually to design heuristic methods to generate them, the replenishment of such strings into a computer population can substantially speed up the solution, thus avoiding the initial "rambling" of an algorithm through a permitted domain. Consequently, the success (fitness) of each string of the population is evaluated obtaining a vector of cost functions values. Then, at least one most fit individual is chosen who is replicated unchanged into the new generation. After that, pairs of parents are chosen based on a selected method, the pairs are then crossed over and some genes of the population mutate. Their offspring, eventually unchanged parents are replicated into the new population. This procedure is repeated until the new population contains a complete number of strings. Consequently, a new generation is formed and a complete cycle is repeated with the new generation until terminating conditions are satisfied. The GA function is realized based on the following steps.: Generating an initial population [P.sub.0].

1) Evaluation of the cost function (or fitness) of each strain in the current (k-th) population [P.sub.k].

2) Testing of GA termination conditions fulfillment. In case they are fulfilled, the most fit individual from the actual population is selected as a resulting solution.

3) If the termination conditions are not fulfilled, the selection of two groups of strings follows. First of all, the group A of the most successful strings, eventually at least one most successful string, of the actual population is chosen. They are replicated unchanged into the new population. Thus, a monotonous convergence of problems is assured--the best solution in the following generation cannot be worse. The group B of the strings chosen by a different method from the actual population (not necessarily the best individuals) is also replicated unchanged into the new population. In principle, the size of this population can be zero. Then, the remaining group C of the strings is selected. The strings can also contain the best individuals. Then, the operations of crossing over and mutation follow.

4) With crossing over, the parental strings of the group C are joined at random, parts of their strings are randomly combined and, as a result, the same number of offspring strings is generated. With mutation, randomly chosen genes of some random strings are changed into random values. After these operations, a new group C of the same size as the group C is formed.

5) A new complete population [P.sub.k+1] is generated as a result of joining the groups A, B, C and the procedure proceeds by the point 2. Terminating conditions of a GA: the evaluation of terminating conditions can be performed by several methods. The most frequently used method of termination is to define a prescribed number of solutions generations. The number can be rather easily estimated after a few runs of the given solution. A similar alternative is to interrupt the GA run and decide if the actual solution is from the user's standpoint satisfying, or it is necessary to continue. Implementation of a genetic algorithm

[FIGURE 6 OMITTED]

5. Possibilities of genetic algorithms application to optimization problems solution

Genetic algorithms application to the defined optimization problems solution was carried out by the authors of the paper. The defined problems were solved by a programmed system MS EXCEL and consequently by the use of a genetic algorithm in order to compare the achieved results. A minimization usually refers to a minimization of a deviation from a required state, a minimization of energy, fuel consumption, losses, costs, negative effects, and the like. Maximization can refer to effectiveness, performance, gain, etc. Another condition of their utilization is the existence of a computer representation of an optimized problem. It means that for any point of the domain being searched, i.e. for any potential solution, it is possible to compute the value of its cost function to evaluate it from the viewpoint of its successfulness, the extent of a required goal fulfillment. The type of the given process, however, is not important it can be of a physical, chemical, biological, economical or a sociological character. For brevity--from the standpoint of an evolutionary algorithm, an optimized problem is a black box providing a great number of more or less reasonable solutions, each of them can be evaluated, e.g. numerically or at least compared to other possibilities from the standpoint of its successfulness. Thus, optimization can be expressed as searching for such a possibility (a set of parameters, structure of interrelations, etc.) which satisfies the determined requirements best. Although it is not always evident at first sight, the problem can be formulated this way even for a very large set of problems which originally ware not formulated as classical optimization problems. Ordinary mathematical and other problems can often be easily transformed into minimization problems or maximization ones. The graph-form representation of the solution by means of a GA /Fig. 7.

[FIGURE 7 OMITTED]

Among the problems that are difficult to solve or even cannot be solved based on conventional optimization approaches and which can be typical applications of genetic, eventually evolutionary algorithms, there are many complicated and/or extensive problems. An important field of the application is engineering. GAs can be a strong means of optimization of electrical circuits, electrification system operation, aerials and filters design, static optimization of technological processes, or a design of automatic control systems. Evolutionary techniques are widely applied to the solution of economical problems which often represent complex problems of both linear and non linear programming with many constraints. Typical applications are transportation or distribution problems, such as searching for the shortest or the cheapest path, other graphically oriented problems, more complex combinatorial problems.

5.1 Application of genetic algorithms to the solution of selected optimization problems

GAs, in general, simulate evolution, where more successful solutions occur in the population of several solutions, i.e. individuals who are replicated into next generations and unsuccessful individuals who extinct. Successfulness evaluation of such individuals is performed based on a suitably defined criterion function a cost function which represents the essence of the optimization problem. The calculations utilize models of basic (biological) genetic operations, such as "crossover", "mutation", "selection". GAs differs from most of classical (conventional) optimization methods in some characteristics. They:

* perform a parallel search in several directions simultaneously,

* do not require supplementary information related to the solution development, e.g. a gradient of the cost function, and the like, require just the evaluation of the cost function in an arbitrary point of the domain being searched,

* widely utilize stochastic processes,

* are able to escape from the space of a local extreme and approach a global extreme,

* are capable of solving optimization problems containing tens or even hundreds of parameters,

* are rather easily applicable to a wide range of optimization problems,

* belong to time consuming or rather complicated problems.

The development of the optimization problems solution showed that some problems were difficult to solve, or could not be solved by the applications of conventional algorithms. Such optimization problems can be solved by the application of evolutionary algorithms, eventually GAs. Typical problems refer to global extremes search of non linear, multimodal problems (with many local extremes) of many variables, combinatorial or graphically oriented problems, multiple parameter problems, where a complexity increases exponentially or factorials, the problems with many constraining conditions, etc. A classical optimization problem is searching for a global extreme of the function of n variables. Let us consider a minimization of the function (the cost function)

J = f ([bar.x]) [right arrow] min [bar.x] = ([x.sub.1], [x.sub.2], ... [x.sub.n]) [member of] [R.sub.n] (11)

satisfying the system of equations and of the inequality:

[g.sub.i] ([bar.x])= 0, i = 1, 2, ..., p [h.sub.i] ([bar.x])> 0, y = 1, 2, ..., p (12)

where the functions f ([bar.x]), g ([bar.x]), h([bar.x]) can, in general, be non linear. In order to solve the defined problem (1)--(3), it is possible to apply a GA. The string elements (genes) will be identical to the components of the vector [bar.x] and the cost function / the objective function will be the function definition f ([bar.x]). In this case, a genetic algorithm can be used in a minimized version. The solution of a GA is often considered a fitness function maximization. That would mean a problem inversion and in such a case the fitness function could be J = -f ([bar.x]) or in case of the fitness positive values requirement

J = a - f ([bar.x]), where a is a large positive number.

Constraining conditions fulfillment is solved, for example, by impermissible strings exclusion from the solution, penalty functions or by other special approaches.

5.2 On some concrete results of optimization problems solutions

The authors were dealing with the solution of various types of optimization problems in MS EXCEL in order to compare the solutions and results to those obtained by the use of a GA in the systems of MATLAB, Tool-box Algorithm and Direct Search, a demo version Mathworks.

Problem 1 The problem of searching for an extreme of the criterion function with the given linear constraints which actually is the problem of a linear programming. The results achieved by the simulation based on a GA were comparable to those achieved in MS EXCEL. The procedure to solve such problems is presented /Fig. 8,/ Fig. 9.

[FIGURE 8 OMITTED]

Problem 2 The problem of searching an optimum path for goods delivery from suppliers to customers. In the literature, the problems of a supplier-consumer type are often presented under the name "problem of a traveling salesman". A supplier goes through all positions on the list, but only once through each position. The positions are mutually interconnected and the distances between them are known. The supplier's goal is to find such a path that enables him to go through all positions only once with minimum costs. In Fig. 8, there is the graph-form representation of contours (equal-scalar lines) of the cost function and the domain of permissible solutions is represented by the given linear constraints as well as the population initial distribution.

[FIGURE 9 OMITTED]

The solution result, i.e. the values of variables x, y can be seen in Fig. 9, the cost function attained the minimum value 8.222. It means that we search for an optimum sequence of individual positions in the string. This refers to a permutation encoding of strings related to the problems where the aim is to find an optimum sequence of elements in the string. It is known that searching for the shortest or cheapest path between the defined points refers to the solution of a transportation problem. Further on, searching for an optimum sequence of operations occurs with a technological procedure optimization or a time table optimization, and the like. A specialty of this problem is that the elements in the string have to occur only once. Consequently, it follows that the use of genetic operations, such as crossover and mutation, is not possible. Let us assume the following situation. A supplier is required to deliver products to the determined positions on the list visiting 20 places, in all. The positions are denoted by symbols A--U. It is obvious that the GA string is formed by an arranged sequence of symbols of individual positions R=[[r.sub.1],[r.sub.2],...[r.sub.20]] , while their sequence from the left to the right represents the sequence in which they are visited. The cost function (fitness) is the sum of the distances between individual positions according to a certain sequence

Fit = [20.summation over (k=1)][v.sup.k,k+1]

where [v.sub.k,k+1] is the distance from the k position to the next (k+1) - st position on the list defined by the given string. In case of a genetic algorithm, it is assumed that a number of generations and populations is selected to solve a defined problem. For the initial solution we select, for example, 1,000 generations and 30 populations. If the achieved results do not satisfy conditions of the problem being solved, in the following solution, according to a genetic algorithm, we will select a higher number of generations and populations. In the former case of the solved problem, 20 positions were considered and in the latter case there were 60 positions. The calculation was performed for 2,000 generations and 510 populations. The results of the problem solution are expressed in the graph-form representation which can be seen in Fig.10 / Fig.11. The defined problem was solved in the system MATLAB, realized through a programmed generating and recording in the M--file system as well as through its consecutive run in the system MATLAB.

[FIGURE 10 OMITTED]

[FIGURE 11 OMITTED]

Problem 3 Optimization of a production plan

In practice, problems of transportation, network analysis, supply optimization, optimization of service systems, renewal activities, etc. are solved most often. These problems are formulated in the form of linear programming problems, where a linear cost function and constraints in the form of equations or inequities occur. However, there also exist optimization problems containing non linear constraints. Basically, a genetic algorithm was used to solve a production plan optimization in which the problem took the form of (1), (2), (3). The aim of such problems solution is to determine an optimum amount of manufactured products and an amount of sets so that the firm or the plant yield can reach the gain maximum value. The results obtained by means of a genetic algorithm were compared to the those obtained in MS EXCEL in order to verify the results. Before a genetic algorithm is used, it is necessary to generate a fitness function in a mathematical model which is a total of the original criterion function and the a multiple of a total of individual constraining conditions. In the solved problems, the a coefficient selection for the fitness function requires some experience with similar problems realization on PC. In addition, the application of genetic algorithms to optimization problems solution requires to perform several experiments in order to improve the solution which is dependent on the selection of the populations number and the generations number which is supported by the presented graphical results (Jadlovska, 2005), (Macura, 2005)

6. Conclusion

The paper presents the representatives of evolutionary computing methods based on which theoretical essentials of genetic algorithms are elaborated. The paper deals with the issues related to mathematical models generating based on the defined notions of isomorphism and homomorphism. It also contains a mathematical and computer model generation as well as the basic stages of a computer modeling. The paper also deals with the essence and a principle of a genetic algorithm, the possibilities of genetic algorithms applications to the solution of the selected optimization problems. The solutions results of the individual problems have been verified comparing them to those obtained by means of a different programmed in MS EXCEL.

DOI: 10.2507/daaam.scibook.2010.42

7. Acknowledgement

This work is the result of the project implementation Development of the Center of Information and Communication Technologies for Knowledge Systems (project number: 26220120030) supported by the Research & Development Operational program funded by the ERDF (75%). This contribution was also designed based on the grant support VEGA No. 1/0345/08: Modelling and Simulation of Mechatronic Systems for Mechanical Engineering (25%).

8. References

Eiben, A. E. & J. E. Smith, J.E. (2003). Introduction to Evolutionary Computing, Springer-Verlag Berlin

Hrubina, K. & Jadlovska, A.(2002). Optimal Control and Approximation of Varionational Inequalities. The international journal of systems & cybernetics, Vol. 31, No. (9/10, 2002), ISSN 0368-492X

Jadlovska, A. & al (2005). Algorithms for Optimal Decision Making and Processes Control. DAAAM International Scientific Book 2005, B. Katalinic (Ed.), 253290, DAAAM International ISBN 3-901509-43-7,Vienna

Macura, D. (2005). Function of Multivariable 1. issue. Presov: FHPV PU, 56 pages, ISBN 80 -8068-321-2

Mitchel, M. (1998). An Introduction to Genetic Algorithms, The MIT Press

Authors' data: Assoc. Prof. PhD. Hrubina, K[amil] *; Univ. Prof. Dipl.-Ing. Dr.h.c.mmt. Dr.techn. Katalinic, B[ranko] **; Assoc. Prof. PhD. Jadlovska, A[nna] *; Assoc. Prof. CSc. Wessely, E[mil] ***; EdDr. PhD. Macurova, A[nna]*; Dr. Majercak, J[ozef] *, * Technical University of Kosice, Letna 1, Kosice, Slovakia, ** University of Technology, Karlsplatz 13, 1040, Vienna, Austria, *** University of Security Management in Kosice, Slovakia kamil.hrubina@tuke.sk, katalinic@mail.ift:.tuwien.ac.at, anna.jadlovska@tuke.sk, emil.wessely@vsbm.sk, anna.macurova@tuke .sk, j ozef.maj ercak@tuke.sk