1
|
- By
- Jeff Breadner & Shabnam Khatami
|
2
|
- Our task was to apply artificial intelligence (AI) concepts to resolve
the problem of unit commitment and loading at the Mica Dam
- Inputs required are power generation for the plant, fore bay elevation,
and unit availability
- Output required is the best unit commitment and loading using the
amount of water and having minimum number of switches used for each of
the next 24 hours
|
3
|
- Currently B.C. Hydro uses a module called the Efficient Unit Loading
Recommendation Program (EULR)
- EULR relies on data generated by Static Plant Unit Commitment (SPUC)
- EULR can generate output in two modes:
- Static – The optimal solution for each hour is output, which is
ignorant of any other hour’s solution
- Dynamic – Attention is paid to the passage of time; each hour’s
solution depends on the other hours’ output
|
4
|
- Genetic Algorithms (GA) are adaptive methods which may be used to solve
search and optimization problems based on the genetic process of
biological organisms – “Darwinian Theory”
- Over many generations, natural populations evolve according to the
principles of natural selection and “Survival of the Fittest” .
- By mimicking these processes, GA’s are able to evolve solutions to real
world problems
|
5
|
- They work with a population of individuals, each representing a possible
solution
- Each individual is assigned a “fitness score” according to how good a
solution to the problem it is.
- The highly fit individuals are given opportunities to “reproduce”, by
“breeding” with other individuals in the population This produces new
individuals as offspring, which share some features taken from each
parent
|
6
|
- The least fit members of the population are less likely to get selected
for reproduction, and thus die out
- A whole new population of possible solutions is thus produced by
selecting the best individuals
from the current generation, and mating them to produce a new set
of individuals
- If the system has been designed well, the population will converge to an
optimal solution to the problem
|
7
|
- GAs are different from more normal optimization and search procedures in
five ways:
- GAs work with a coding of the parameter set, not the parameters
themselves
- GAs search from a population of points, not a single point
- GAs use probabilistic transition rules, not deterministic ones
|
8
|
- .GAs use payoff (objective function) information, not derivatives or
other auxiliary knowledge
- GAs work from a rich database of points simultaneously (a population of
strings), climbing many peaks in parallel; thus, the probability of
climbing a false peak is reduced over methods that go from point to
point
|
9
|
- A simple GA that yields good results is composed of three operators:
- Reproduction
- Crossover
- Mutation
|
10
|
- During reproduction, population members are copied according to their
fitness function values
- This fitness function can be thought of as a process of measuring the
members’ profit, utility, or benefit that we want to maximize
- Members with a higher fitness have a higher probability of ‘mating’ with
other members
|
11
|
- Crossover can be thought of as the process of ‘mating’
- Segments of the parent’s ‘gene sequence’ strings are mixed, creating
children that are composed of parts of their parents
- The process of reproduction and crossover are repeated, giving the
children fitness values and giving them the opportunity to ‘mate’
|
12
|
- During mutation, random ‘genes’ in chromosomes are changed
- Mutation plays a decidedly secondary role in the operation of GAs
- it provides the guarantee that the probability of searching any given
string will never be zero and acting as a safety net to recover good
genetic material which maybe lost through the action of reproduction and
crossover
|
13
|
- The GA simulation is terminated when the fitness of the best or average
population remains the same for 2-3 successive generations
|
14
|
- To represent one unit commitment solution for one hour, the following
method was used:
- G4 G3
G2 G1
- on on
off on
- 1 1 0 1
- This 1101 in binary is 13 in decimal; the same method is used to code
all combinations into a ‘combo number’ that represents the status of
each unit in the plant
|
15
|
- In order to create a ‘chromosome’ that would solve the entire 24-hour
problem, a
- 24 x 4 = 96 byte long gene
would be required
- This was regarded as being too long, so we decided to solve for 4 hour
segments at a time, utilizing 4 x 4 = 16 byte long chromosomes instead.
For each successive run, we can use the status of the pervious 4 hours
in our previous run, making the problem to be solved in a
dynamic-programming way
|
16
|
- Thus, one of our chromosomes could appear like this:
1011010111001011 - chromosome
- 1011 0101 1100 1011
- These combo #’s correspond to hour 1, 2, 3 and 4 respectively
|
17
|
- Our Fitness Function is structured of two
- parts:
- Water use Number of Switches
- Where W1=0.6,
W2=0.4, Qmax=1902cms, Nmax=16
|
18
|
|
19
|
|
20
|
- Using the SPUC table as a database in EXCEL to find the amount of water
used for each hour given the inputs.
- Using the table of number of switches to find the number of switches for
each successive hours.
- Satisfying the constraints by giving a high number to infeasible combos
in these two tables
|
21
|
- Firstly, a population of 100 chromosomes is randomly generated.
- Each chromosome is assigned a fitness score
- A chromosome's probability of mating is
|
22
|
- Once population members are selected for reproduction, a random
crossover point is selected (a crossover value of 6 is demonstrated
here)
- 0011010101101010 1001011100110110
- 1001011100110110 1001010101101010
|
23
|
- Each set of parents is assigned a random crossover, and generates two
children
- These children form the second generation, and are fed back into the
first part of the algorithm
- The algorithm currently loops a fixed number of times
- Results are fed into the user interface
|
24
|
- The User Interface contains a controller which reiterates through the GA
module to get information for all 24 hours
- Once a combination is selected for each hour, the user interface is
displayed summarizing the information for each hour
- It gives the user a chance to review the information generated and also
gives an opportunity to modify the hourly combos
|
25
|
|
26
|
|
27
|
|
28
|
|
29
|
- The GA Fitness function needs to be refined
- This is the most important factor to the viability of this approach
- Consideration of unique conditions needs to be built into the fitness
function via a third component
- The GA Engine can be completely rewritten
- The current engine is based on the “ideal” GA algorithm; it actually
manipulates gene strings in Excel, while it would be more efficient to
manipulate arrays of combo numbers internally
- In rewriting the engine to handle arrays of numbers instead of gene
strings, longer chromosomes could be feasible (up to the whole 24
hours)
|
30
|
- The entire project should be moved from Excel/Visual Basic to a
stand-alone language like Visual C++ or Delphi
- These languages have the ability to connect over a network to database
servers, ideal for an enterprise-networked environment like B.C. Hydro
and PowerEx
- There would be incredible speed improvements over the Excel/VB
implementation
|
31
|
|
32
|
- Using Genetic Algorithms to solve the Unit Commitment & Loading
problem could be feasible with more work
- In development, attention should be paid to:
- Refining the fitness function
- Incorporating unique conditions
- Developing or obtaining a better GA Engine
|