«Using the model of genetic algorithms for optimization purchases at the enterprises»

Every year business becomes more flexible, mobile and changeable. Thing that was optimum literally yesterday, today can appear very distant from an ideal. On principle new possibilities appear quite often, missing out which it is possible quickly to fall behind from competitors, and even quite to «take» off from business — examples to the last, unfortunately, mass. And all from adherence by a withstand, «tested time» to the charts, inability to think not only tactically but also strategically.

A most effect is today arrived at not so much by the produced connections, how many by the maximal use of market mechanisms and above all things competitive activity of suppliers. In fact business in modern market conditions is very similar with battle actions, frequently conducted at once on a few fronts. Therefore mobilization of all forces and facilities is a mortgage of not only achievement of success in competitive activity but also survival of company.

It is possible to select a few stages of introduction to the fight of backlogs:

• «extensive» backlogs of growth — expansion of production, bringing in of investments and t. of d.;
• then the «intensive» are maximally used is introduction of new technologies, marketing’s, project, construction and designer decisions, standards of quality; teaching of employees and t. of p.;
• when and all is outspent here, the pore of reorganization of business comes is the use of modern administrative methods up to total reengineering of all business-processes.

When the level of competitive activity arrives at a maximum and all backlogs are already involved, it is necessary to search the additional sources of optimization of economic activity. And one of main factors, determining success, there is efficiency of the use of all resources: beginning from consumable raw material and materials (including office commodities even) and concluding services of external consultants.

In international practice as a basic instrument of acquisition of commodities, works and services tender auctions are examined. A general chart is presented on a picture 1. An order and terms of lead through of auctions is regulated the generally accepted international norms and rules, which are formulated and expressed in the rules of lead through of purchases of large international organizations, financial institutes and donor agencies.

Picture 1 - General chart of procurement.

Sense of auctions consists in the receipt of commodities, works and services for the least cost at optimum quality. Already in itself this assertion is contained by supposition that a determinative at the choice of winner of auctions is correlation of price and quality in the suggestion presented an applicant. However, importance of these two factors depending on the article of auctions is different, that is conditioned the features of the article of auctions (commodities, works or services) and positions of tender document, applied for the leadthrough of concrete auctions.

There was a period in history of tender practice, when the winners of auctions were determined exceptionally on the basis of the least ascable price. This method of choice appears very simple and effective, however, to a posteriori implementations of the contracts concluded on such method, customers understood quickly, that the least price quite not necessarily meant necessary quality and can be the unique determinative only on occasion, when brought over to participating in auctions suppliers, contractors or consultants, well enough know a customer as performers, stably providing the required level of quality. On this account, as far as development of tender procedures, customers were forced to enter in competitive documents additional requirements in quality, which could become determining in a number of cases.

One of the most important and difficult tasks in the estimation of suggestions, and perchance and holdings competition, there is a choice of winner. Certainly, it can show oneself elementary, if the question is about a choice one by one to the measurable criterion, to such as a price, and even on to-three.

But criteria are more usually, and part from them not quantitative, but high-quality, which formalize is very hard frequently. Besides not always obviously, as far as these criteria are independent of each other.

The very much methods of choice of the best variant (suggestions) are developed, because this task is actual for most spheres of human activity, rather than just for competitive purchases. There is even separate discipline is a theory of making decision, which powerful mathematical models are developed within the framework of, such as a method of analysis of hierarchies.

However in purchase practice used more frequent than all:

• price estimation;
• numerical score;
• soft rating;
• expertly-mark estimation;
• minimum price at conforming to the qualifying requirements.

Application of other methods is rather exotic things, as for their realization thorough enough mathematical knowledge and logic of calculations are required not transparent for most members of competitive commission, by these knowledge of not possessing. Besides the use of mathematical methods requires independence and formalization of the compared criteria, that frequently problematic.

Genetic algorithms are highly parallel mathematical algorithms that transform populations of individual mathematical objects (typically fixed-length binary character strings) into new populations using operations patterned after natural genetic operations such as sexual recombination (crossover) and fitness proportionate reproduction (Darwinian survival of the fittest).

Genetic algorithms begin with an initial population of individuals (typically randomly generated) and then, iteratively, evaluate the individuals in the population for fitness with respect to the problem environment and perform genetic operations on various individuals in the population to produce a new population.

John Holland presented the pioneering formulation of genetic algorithms for fixed-length character strings in Adaptation in Natural and Artificial Systems (Holland 1975). Holland established, among other things, that the genetic algorithm is a mathematically near optimal approach to adaptation in that it maximizes expected overall average payoff when the adaptive process is viewed as a multi-armed slot machine problem requiring an optimal allocation of future trials given currently available information.

In this work, Holland demonstrated that a wide variety of different problems in adaptive systems (including problems from economics, game theory, pattern recognition, optimization, and artificial intelligence) are susceptible to reformulation in genetic terms so that they can potentially be solved by the highly parallel mathematical genetic algorithm that simulates Darwinian evolutionary processes and naturally occurring genetic operations on chromosomes.

Genetic programming is a domain independent method that genetically breeds populations of computer programs to solve problems by executing the following three steps:

• Generate an initial population of random computer programs composed of the primitive functions and terminals of the problem.
• Iteratively perform the following substeps until the termination criterion has been satisfied:
• Execute each program in the population and assign it a fitness value according to how well it solves the problem.
• Create a new population of programs by applying the following two primary operations. The operations are applied to program(s) in the population selected with a probability based on fitness (i.e., the fitter the program, the more likely it is to be selected).
• Reproduction: Copy an existing program to the new population.
• Crossover: Create two new offspring programs for the new population by genetically recombining randomly chosen parts of two existing programs. The genetic crossover (sexual recombination) operation (described below) operates on two parental computer programs and produces two offspring programs using parts of each parent.
• The single best computer program in the population produced during the run is designated as the result of the run of genetic programming. This result may be a solution (or approximate solution) to the problem.

Animation 1 - Flow-chart of Genetic Algorithm (22 clips, loop 2 times).

I believe the single most important area for future work in genetic programming (as well as for all other techniques of automated machine learning) is to demonstrate the applicability of the technique to realistic problems.

The presence of some or all of the following characteristics make an area especially suitable for the application of genetic programming:

• an area where conventional mathematical analysis does not, or cannot, provide analytic solutions,
• an area where the interrelationships among the relevant variables are poorly understood (or where it is suspected that the current understanding may well be wrong),
• an area where finding the size and shape of the ultimate solution to the problem is a major part of the problem,
• an area where an approximate solution is acceptable (or is the only result that is ever likely to be obtained),
• an area where there is a large amount of data, in computer readable form, that requires examination, classification, and integration, or
• an area where small improvements in performance are routinely measured (or easily measurable) and highly prized.

For example, problems in automated control are especially well suited for genetic programming because of the inability of conventional mathematical analysis to provide analytic solutions to many problems of practical interest, the willingness of control engineers to accept approximate solutions, and the high value placed on small incremental improvements in performance.

Problems in fields where large amounts of data are accumulating in machine readable form (e.g., biological sequence data, astronomical observations, geological and petroleum data, financial time series data, satellite observation data, weather data, news stories, marketing databases) also constitute especially interesting areas for potential practical applications of genetic programming.

The fundamental importance of optimization problems guarantees that there will be considerable future work on applying genetic programming to optimization.