04-12-2012, 01:59 PM
optimization algorithms
optimization algorithms.docx (Size: 193.98 KB / Downloads: 21)
ABSTRACT
In this real world there are some problems that can be solved in the polynomial time and their time of execution increases in polynomial fashion with the increase in the size of the problem.
But some problems for which the computation time increases in the exponential manner with the increase in the size of the problem such kind of problems are known as N-P hard problems. The solution to the N-P hard problems can be obtained (it may take a lot of time) but there is no surety about the solution to be an optimal solution. Hence we need to have such an algorithm that can provide more optimal solution than the solution for NP hard problems obtained by any other existing algorithm.
Here the problem of the graph-partitioning has been taken up in this project because the partitioning of the graph is also an N-P hard problem in itself. KL-Algorithm is the pioneer of the graph partitioning algorithms
Introduction
Optimization is indispensable for any engineer. Every process needs to be optimized but this is not a straight forward task. There is a need of optimization techniques that can bring efficient and global results. There are several problems with traditional optimization techniques. As and when the complexity of the system increases they become intractable and impossible to solve. Moreover they are unable to handle highly non-linear functions and sharp points where the function is not differentiable. Here lies the importance of a robust optimization technique that is able to deliver global solutions for any type of problem.
Historically, one of the main driving forces behind the development of electronic computers was the desire on the part of scientist and the engineers to solve problems that were too complex to solve any other way. The computational procedures for doing this sort of thing became to be known as optimization algorithms. They did not always work most often because the problem under analysis either did not have a well defined optimum, or was otherwise ill-behaved. But in certain specialized areas in engineering and physics, computer optimization proved to be very useful.
Motivation for using EAs and QEAs
Evolutionary Algorithms are a class of solutions developed by computer scientists to solve difficult problems. Evolutionary computing uses procedures that overcome many of the disadvantages that conventional optimization algorithms have. As the name implies, evolutionary computing uses concepts borrowed from Darwinian evolution to "breed" good solutions to design problems. Although the details of how evolutionary computations work can be complicated, the basic ideas are simple.
EAs are often viewed as a global optimization method although convergence to a global optimum is only guaranteed in a weak probabilistic sense. However, one of the strengths of EAs is that they perform well on "noisy" functions where there may be multiple local optima. EAs tend not to get "stuck" on local minima and can often find globally optimal solutions. EAs are well suited for a wide range of combinatorial and continuous problems.
Scope of the project:
Efficient designing of any complex system necessitates decomposition of the same into a set of smaller subsystems. Subsequently, each subsystem can be designed independently and simultaneously to speed up the design process. The process of decomposition is called partitioning.
In this real world there are some problems that can be solved in the polynomial time and their time of execution increases in polynomial fashion with the increase in the size of the problem.
But some problems for which the computation time increases in the exponential manner with the increase in the size of the problem such kind of problems are known as N-P hard problems. The solution to the N-P hard problems can be obtained (it may take a lot of time) but there is no surety about the solution to be an optimal solution. Hence we need to have such an algorithm that can provide more optimal solution than the solution for NP hard problems obtained by any other existing algorithm.