Author Topic: Resource Allocation Using Genetic Algorithms  (Read 2290 times)

0 Members and 1 Guest are viewing this topic.


  • International Journal of Scientific and Engineering Research
  • Administrator
  • Jr. Member
  • *****
  • Posts: 89
  • Karma: +0/-1
  • Research Paper Publishing
    • View Profile
    • International Journal of Scientific and Engineering Research
Resource Allocation Using Genetic Algorithms
« on: January 22, 2011, 05:54:24 am »
Author : S. Ranichandra, T. K. P. Rajagopal
International Journal of Scientific & Engineering Research, Volume 1, Issue 2, November-2010
ISSN 2229-5518

Many business and economic situations are concerned with a problem of planning activity. In each case, there are limited resources at the disposal and the problem is to make use of these resources so as to yield the maximum production or to minimize the cost of production, or to give the maximum profit, etc. Such problems are referred to as the problems of constrained optimization.

LPP is a technique for determining an optimum schedule of interdependent activity in view of the available resources. The term "programming" means "planning" which refers to the process of determining a particular plan of action from amongst several alternatives. The general form of a LPP is described as follows. Let z be a linear function on Rn defined by
z = c1x1 + C2X2 + .. . + cnxn                     … (a)
where cj’s are constants. Let (aij) be an m x n real matrix and let {b1,b2.. . bm} be a set of constants such that
a11X1 + a12X2 +.... + a1nXn>= or<=or = or> or<b1
a21X1 + a22X2 + ... + a2nXn >= or<=or = or> or<b2
am1x1 + am2X2 + . . . + amnxn >= or<=or = or> or<bm

and finally let
Xj>=0;j = l,2,3,...n                 … (c)

The problem of determining an n-tuple (x1, x2, . . . xn) which makes z a minimum (or maximum) and which satisfies (b) and (c) is called the general LPP.

The objective of the GAs is to find an optimal solution to a problem. Of course, since GAs is heuristic procedures, they are able to find very good solutions for a wide range of problems. GAs work by evolving a population of individuals over a number of generations. A fitness value is assigned to each individual in the population, where the fitness computation depends on the application.

The main advantages of Genetic Algorithms are:
•   They are adaptive
•   They have intrinsic parallelism
•   They   are   efficient   for   complex problems

This paper provides a GA based solution to LPP. GAs have been applied to many diverse areas such as Function optimization, VLSI circuit design, Job Shop scheduling, Bin packing, Network design, Transportation problems and etc.

Genetic Algorithm was invented by Professor John Holland at the University of Michigan in 1975. It was then made widely popular by Professor David Goldberg at the University of Illinois. The original Genetic Algorithm and its many variants are collectively known as Genetic Algorithms. GAs are general-purpose search techniques based on principles inspired from the genetic and evolution mechanisms observed in natural systems and populations of living beings. Their basic principle is the maintenance of a population of solutions to a problem {genotypes) in the form of encoded information that evolve in time. The evolution is based on the laws of natural selection (survival of the fittest) and genetic information     recombination     within     the population. The evolving population samples the search space and accumulates knowledge about the good and bad quality areas and recombining this knowledge to form solutions with optimal performance to the specific problem[l].
At first a population of M solutions does a generated at random, encoded in string of symbols (preferably binary strings) resemble natural chromosomes. Each member of the population is then decoded to a real problem solution and a "fitness" value is assigned to it by a quality function that gives a measure of the solution quality. When the evaluation is completed, individuals from the population are selected in pairs to replicate and form "offspring" individuals (i.e., new problem solutions). The selection is performed probabilistically. When two parents are selected their symbol strings are combined to reproduce an "offspring" solution using genetic-like operators. The main operators used are Crossover and Mutation. Crossover simply combines the parent symbol strings forming a new chromosome string that inherits solution characteristics from both parents. Mutation covers this need by injecting new information in the produced string. The injection is done by randomly altering symbols of the new chromosome. Generally mutation is considered as a secondary but not useless operator that gives a non-zero probability to every solution to be considered and evaluated.
When M new solution strings are produced, they are considered as a new generation and they totally replace the "parents" in order for the evolution to proceed. Many generations are needed for the population to converge to the optimum or a near-optimum solution, the number increasing according to the problem difficulty.

Read Complete Paper: