Resource
Optimization
The knowledge based capabilities
of XpertRule® Knowledge Builder provide powerful facilities
for complex decision making solutions. But, what if your objective
is to find an optimal or a valid solution? Something of a reverse
decision process is required to find the combination of variable
values that will achieve the best result or best fit. Problems such
as planning, design, blending and resource scheduling typically
fall into this category.
The Genetic Algorithm Optimizer within Knowledge Builder
can be used to determine optimal solutions to problems that have
many possible solutions, such as design, resource scheduling and
planning, and component blending. You do not have to tell Knowledge
Builder how to solve the problem - instead you specify a method
of evaluating solutions, define the constraints on resources and
Knowledge Builder will evolve the best possible solution
according to your criteria.
Several approaches have been used to solve these types of problems,
with varying levels of success:
- Try every possible combination and evaluate the best result.
This works fine, but with real life problems the number of combinations
is usually so large that this approach is not practical given
a reasonable time scale.
- Use a Knowledge Based System approach to narrow down the solutions
worth investigating. While this approach can give reasonable solutions
it is often unable to find near optimal solutions, particularly
when constraints are defined. If the solution strategy you pick
is poor, the results will be poor.
- Use linear programming techniques. These can work well when
optimizing the numeric parameters of a recipe type problem. However,
in resource scheduling and planning it becomes very difficult
to represent the problem in terms of linear numeric parameters.
Evolving solutions
Knowledge Builder solves optimization by a very different
approach - using Genetic Algorithms. These provide an advanced alternative
to the approaches listed above.
How Knowledge Builder Optimization works:
- Randomly generate a limited number of possible solutions. Not
all possible solutions, which is impractical, but a starting group
- an initial generation.
- Assess the quality of these random solutions.
- Crossbreed solutions with more emphasis on better solutions.
- Randomly alter (mutate) some of the solutions, to introduce variations.
- Continue the natural selection process until good solutions evolve.
These techniques are inspired by the theory of biogenetics and
evolution. Using Genetic Algorithms for optimization:
- Avoids the need to design a strategy to converge towards a solution.
The developer only needs to design a cost or fitness function
to evaluate each solution considered by the algorithm. Good solutions
evolve by 'natural' selection.
- Allows the developer to impose constraints (or weighted penalties)
for parameters not being satisfied by the solutions. This has
the effect of 'killing off' bad solutions.
Hybrid systems
Many complex applications will require both Knowledge Based Systems
and Optimization to be used. The Knowledge Based System element
can be used to decide on the values to be set for constraints, or
to process optimized results further. It can also be advantageous
to have the Knowledge Based System 'narrow down the universe' being
presented to the optimization process - in other words to plant
the seeds for good solutions in the initial generation. The potential
of such powerful hybrid systems is unique to Knowledge Builder
developers. For example, such hybrid systems allow the optimization
engine to call external cost evaluation functions implemented as
Dynamic Link Libraries (DLLs).
The paper by Dr Al-Attar, "A Hybrid
GA-Heuristic Search Strategy", gives a technical insight
into hybrid systems.
|
