Welcome to another session of Smart Energy Distribution.
My impression is that the changes in location and time somehow have
led to a reduction in the number of participants, but I hope that that
will stabilize again in the next weeks, because this was the preferred
time of most of you.
And so I was told that the old time was a problem because quite a few
of you had conflicting other appointments there and so you couldn't
come.
And now only a subset of those who have been there on Thursdays is
here on Monday afternoon.
So I hope that this will stabilize in some way.
The room has been communicated in time, I think.
I didn't notice any problems with that.
I could certainly briefly try to see...
I don't know whether in the forum there was any discussion on this.
Did you check that?
No discussion in the forum.
Okay, then I'll just go down with this here.
So let's come to the contents of the course.
So today we will have two lectures in sequence because there had been
a few times where the course had to be canceled because I was not
there.
And now we will continue with the topics that we have looked at last
time.
Last time we had started to look at the balancing of power in...
Let me just briefly go back to what we had...
I always have to do that.
Briefly go back to what we had done the last time.
And there we had looked at the electric power distribution.
We had looked again at the power distribution.
And there we had in particular looked at pricing and energy end use
and so on.
You remember that we had looked at several different things there.
I had shown you something on energy conversion technologies, power
generation from fossil fuels.
We had looked at the problem of the changes with respect to the
previous or the traditionally very stable separation into base load,
medium load, and peak load, which is no longer really the adequate way
of looking at the power problems.
And in particular some people always talk about the necessity to do
something like peak shaving.
So they talk about we have to reduce the peaks in energy consumption.
And this is completely out of scope meanwhile, because what we have to
reduce is the deviation from the preferred power profile.
And the power profile can actually demand for consumption peaks at
certain times of the day.
And we have to look at minimizing the deviations from the preferred
profile, which can mean that it is reasonable to have peak shaving,
but this is just one aspect.
And then we looked also at the renewable energy generation, power
generation, looked at the different aspects of the power mix, looked
at wind power, looked at biomass.
And I showed you something with respect to the transmission
distribution networks.
We had looked at that again, slides that you had seen before already.
And then we looked at the different voltage levels, objective to
minimize the transmission loss.
We looked at AC versus DC, looked at the different networks, logical
structures, and then looked at the balancing zones and so on,
balancing power.
We did that the time before.
That was what we looked at last time.
The energy market structures, I showed you something about the prices
that develop, that sometimes we have very dynamic pricing levels,
sometimes not that dynamic in particular, sometimes very low prices.
I showed you something about merit order.
The development of the prices, which are going down, which means that
for the industry, it is a problem to get the expenditure refinanced,
so to make a profit is difficult, and that's why they are
concentrating on decentralized energies.
I showed you something about the electricity prices for private
customers, for the industry, and we noticed in particular that if the
industry doesn't have to pay the EEG fee, then they are really in a
very competitive situation compared to other countries.
That was everything we had in that chapter, and then we came to
chapter 3, where I showed you something about the logical structure of
the power grid, about the task or the balancing groups.
The problem that you don't know whether you get money for having a
surplus of energy or whether you have to pay for that, and that's why
people try to actually have very small deviations from the predicted
power profile.
We looked at price signals, ways to actually achieve a balancing.
We showed at this slide here, I think this was... we had seen already
this slide, and I think that was it.
What did we go further than that?
I think we did go further than that.
Yes, I showed you something about the avalanche effect that we have if
we have only prices to control the energy.
The idea is that we should try to reduce the deviations from preferred
profiles and do that by appropriate negotiations between the different
partners in the system.
I showed you particular devices where we can't do something, so the
devices should know something about their status.
That was the example of a fridge and potential ways of actually
getting flexibility into the power schedule of a fridge, which is not
that difficult to do.
In particular, this is just one example of many devices, like heat
pumps or freezers or ice houses, like large cooling houses, which
actually have this capability of just having to support a certain
range of temperatures.
This temperature range has to be supported, so you have some
flexibility.
As long as the temperature stays in between the corridor, you can
modify the times at which you actually use power.
And then we came to actually using the device pool for controlling the
balance between demand and supply.
I showed you that all the devices should actually provide some
information on the way they actually would intend to use power in the
future.
So they offer certain alternatives, like the fridge or the combined
heat and power plant or washing machine.
And if you know those flexibilities, those different possibilities for
actually using the devices, then you can try to actually satisfy the
demand for power consumption, which has to fit into that red indicated
rectangle.
And this is the first new slide, actually, where we look at the
algorithm that is actually used.
This is what we have to do.
Why doesn't it go backwards?
Something is strange here.
I don't know what's happening.
So this was the previous slide.
We have to optimize this.
And one way of optimizing this, that means satisfying a certain bin
packing problem.
Do you know what a bin packing problem is?
Most of you know that.
Some don't.
But it's just some optimization problem to put a sufficient number of
items into some bag or some bin such that you can exactly fill the
capacity or fill the capacity at the best possible way.
And here you have a certain... you're not filling the rectangle in the
best possible way, and you have to try to optimize that.
And for that, we actually use in this approach here an evolutionary
algorithm.
And an evolutionary algorithm has the following idea that is derived
from things we know from nature.
So we know certain things that happen in evolution.
And this is just taken over or transferred into algorithms.
And so what we do is we generate a certain population.
All these rectangles here in this population, so if we have here these
colored rectangles, are just some representations of solutions to a
problem.
Our problem was we have this power schedule, we have a certain amount
of power that is generated, and we have to find for an appropriate
packing of different elements such that this area is completely
filled, such that we have a complete balance between demand and
supply.
So every such filling of that rectangle would be one possible
solution.
There could be different devices that are activated.
And so we have initially some random population, random solutions.
Not all of them might be feasible.
We had seen on the previous slide that sometimes you might get
something which looks like this, which is not really feasible, or
something like that, would be too large, doesn't fit, so you have to
do something about it.
You have to evaluate.
So what we do is we have to evaluate the population.
That means with respect to a certain objective function that we have,
usually just one objective function.
Sometimes we have several objective functions, not just one.
So maybe it's not only the case that we would like to fill that
rectangle, but maybe we would like to have only power from renewable
sources.
So we have to optimize the amount of renewable sources that is needed.
Might be another objective.
Here we assume we have just one way of evaluating, and then we select
certain parents.
Now we select parents depending on their quality, but we do that in a
randomized way.
So when we have some operation here, select parents, it means that
there is some randomized operation which selects certain parents.
Parent immediately means that you're only a parent if you have
offspring, so you have to create children.
Create children means you have to take two elements, or at least two
elements, and produce offspring by recombination.
And then afterwards you have another operation that is present in
nature, which is mutation.
So we mutate the children, modify them slightly.
This is recombination.
So you see here indicated that, for example, here those two are
combined, and you get something which is...
or if these are...
you have just some elements from the two just recombined in some
reasonable way.
And we will see that a little bit later how that actually functions.
Then we have mutation.
Certain information here, for example, this one is modified into
something else.
So you see here slightly different elements because they are modified
randomly.
Mutation, and then you have the next evaluation, and you perform some
ranking or rating.
You evaluate these offspring, and from having the old population and
the offspring, you decide which of those actually have to enter the
new population.
So from those offspring elements and the old population, you generate
the new population, and then after that, you find out whether some
termination condition is satisfied.
If it's satisfied, so this is the evaluation of the children, if the
termination condition is satisfied, you terminate, you stop, and you
just take the best solution that you had already.
Otherwise, you continue, you select the population for the next
generation, select parents again, create children, and so on, and this
is iterated as often as you like, and usually as you like means as the
termination condition tells you that you should continue, which can
mean that you just have no changes over several generations, or you
have no improvement anymore, and so at some time you just stop.
Or maybe you have a fixed number of iterations, you say just 20
iterations, and that's it, and then you take the best possible
element.
Now let's do that a little bit more in detail, I just indicated it
following that illustration.
So in general, evolutionary algorithms are just a metaheuristic used
for optimizing certain systems, so we have an optimization problem
with respect to one or several objective functions, and I will not
consider here multi-objective optimization, although that is easily
done, in particular evolutionary algorithms are very well suited for
dealing with multi-objective problems.
So we would like to have the best possible solution, and the problem
is that very often we have very limited knowledge about
characteristics of the search space.
So if you know exactly that you have a certain function, maybe looking
like this, if this is the quality of your elements, you can easily
just find the optimum value, if you assume you would like to minimize
that function, the optimum value would be down there, and so that
would be a simple optimization.
But for that you have to know that your search space and your fitness
space actually has exactly that shape.
But usually we don't know that, quite often we don't know that, we
cannot really utilize any knowledge about the fitness space, the
evaluation space, and so since we don't know really how to describe
the function, we can evaluate at each point, but we don't have a
closed form for the function, so we don't have knowledge really.
And for that it is a good idea to use a method which can deal with any
optimization problem, where you are just able to actually in some way
determine the quality or approximate the quality of a certain
solution, and then do some optimization based on that.
Now, typically those problems certainly should be quite difficult, so
if it's a simple problem you can just do a complete enumeration, use a
brute force approach, or if you have a simple problem, as I said here,
you would have better methods.
There should be at least an NP-hard.
Who of you doesn't know what an NP-hard problem is?
You don't know what an NP-hard problem is.
Okay, so I have to tell you very briefly what an NP-hard problem is.
Now this would be the task of one, two lectures to actually tell you
what that is, but I can try to do it in a very simple way.
For example, let me take the example of a traveling salesperson
problem.
Traveling salesperson problem is the problem where you have different
cities, and like I mentioned that several times already, and you would
like to find the best possible tour through those cities.
Those are the cities, these are just crossing lines.
The best possible tour leading through all the cities without visiting
any city twice, and it should be the shortest path.
So you might have different possibilities, and so the question is, how
can I find the best tour?
Or can I find a tour which is shorter than a certain limit?
A tour length less or equal some value k, for example.
That's what you ask.
Do we have some possibility to find a tour length which is less or
equal a certain number?
Now, to find such a tour, to determine those which are actually less
or equal that k, is a difficult problem.
It takes some time.
And the interesting thing is, we can, for example, guess some tour.
I could guess this tour, or I could guess a different tour.
I could say, okay, I would like to have, let's say I take this tour,
where I connect those, that one, that one, that one, that one, that
one.
Different tour, also connecting all the different cities.
And I can, for each tour that is there, that I can generate, I can
evaluate the length actually in time linear to the length of the tour.
So every, we have on every tour, on every edge, we have a certain
distance value, d, i, j, if this is i, if this is j.
So we have distances on all the edges, and so we are looking for a
tour that has the shortest length, so we just have to add all the
distances, and then we have the value for the length, and we can
check, is that less or equal k.
Now, to compute that length is a simple problem, linear in the number
of cities.
But just by guessing, we cannot make sure that we actually find that
one.
The number of different tours that we would have to look at in order
to find really the one that has smaller length is exponential, the
number of possible tours, all the different tours that are possible,
you can easily see this is a permutation problem, and so there are
many different possibilities.
So if you have a deterministic algorithm, which would check all the
possibilities and try to find out whether there is a tour having that
length, the deterministic algorithm would take exponential time, at
least the algorithms that we know of for this problem would take
exponential time if they are deterministic.
A non-deterministic algorithm, where we just guess a solution and then
evaluate that solution, is a non-deterministic algorithm where the
evaluation takes polynomial time.
And NP stands for non-deterministic or having...
the problem can be solved by a non-deterministic Turing machine.
A Turing machine is a theoretical device for performing computations
in polynomial time, so non-deterministically in polynomial time.
That is NP.
And there are actually other problems which run in polynomial time on
deterministic Turing machines.
So you have a deterministic algorithm which runs in polynomial time.
For example, to add up all the distances of a path is a linear time
algorithm, or to perform a matrix multiplication is a polynomial time
algorithm.
N cubed for N times N matrices.
The interesting point is if we have non-deterministic algorithms
running in polynomial time and deterministic algorithms, what about
the relationship between those two classes?
All problems where the solution can be guessed and evaluated in
polynomial time, or those that are deterministically solvable in
polynomial time, are these actually the same classes?
Are they different?
We don't know that.
All the algorithms we know of, there we have a huge gap, oops, that
way, a huge gap, but it may just be that we don't have the right idea
for those algorithms.
So NP is the class of all those problems where you can guess a
solution and evaluate your objective function on that in polynomial
time.
Another question is how can we deal or how can we describe those
problems in a reasonable way if we would like to find out, is that
really a hard problem?
And a hard problem is a problem where problem X would be called hard
with respect to NP if we can take any problem from that and map that
onto this problem in polynomial time and then take a solution to that
problem X, let's say this is problem Y here, and transform that
solution of problem X into a solution of our problem Y.
If that is possible, as I said, to transform is just a problem here,
an arbitrary problem of NP in polynomial time into X, such that the
solution to problem X can be transformed in polynomial time into a
solution of that problem Y.
If that holds for all the problem in NP, then this problem X here is
at least as difficult as all the problems in NP.
If you can do this with all the problems in NP, we have a problem X
which cannot be simpler than the problems in NP, like significantly
simpler.
And so we say that such a problem is actually NP-hard.
So such a problem X would be called NP-hard.
That means it is at least as difficult as all the problems in NP, up
to polynomial differences.
That's this polynomial reduction.
And then maybe that this problem itself, this problem X here, is
itself a member of NP.
And then X would be called NP-complete.
And so it would mean that X is a problem which is actually at least as
hard as any problem in NP, and itself it is in NP.
That means it belongs to the hardest problems in NP.
And now we have here this example up here, NP-typical, NP-hard,
actually NP-complete problems, like the traveling salesperson problem,
project scheduling problems.
There are many scheduling problems which are NP-hard, which are
difficult to solve, at least up to our current knowledge.
We don't have deterministic algorithms which can solve those problems
in polynomial time.
All we have are approximations which might run in polynomial time, or
we have some non-deterministic approaches.
And for those algorithms where a deterministic version would need
exponential time, for those problems it might pay off to use the
evolutionary algorithms.
So those are NP-hard problems.
If you like to learn more about that, look up the typical textbooks on
algorithms, or come to my introductory course on informatics, or go to
some other course on algorithmics.
So you find many textbooks, many statements on that class of problems.
So it means it is a difficult problem.
Known deterministic algorithms need, in the worst case, exponential
time, and so are not feasible for large problem instances.
But if we have some heuristics available, maybe we can get close to
the optimal solution.
So what we have here, if you follow this idea of evolutionary
algorithms, we do a systematic randomized search, which is inspired by
things we have seen in nature, like methods of evolution, using
crossover, mutation, some selection methods, selection of the fittest,
and so on.
We know methods like typical greedy algorithms, like hill climbing and
things like that, local improvements.
We can use those technologies, but these will not guarantee an optimal
solution.
It will only lead to some well-performing areas in the search space.
If you are lucky, you get the optimum.
We have many examples where we actually can successfully use
evolutionary algorithms to get optimum solutions, but we cannot
guarantee to get that, because it's a randomized algorithm.
It's just some random search, but done in a clever way.
And I will have to look further into that, just to show you the
individual components of that.
Now there are many different versions of evolutionary algorithms.
There are the so-called genetic algorithms, there are evolutionary
strategies, or evolution strategies, there's evolutionary programming,
there's genetic programming.
They all have different characteristic elements, but the basic ideas
can be summarized with what I had shown you on the previous slide
here.
That is essentially the algorithmic pattern of the evolutionary
algorithms.
Also evolutionary programming, evolution strategies, and so on.
Just the way you actually represent your elements, the way you perform
crossover and mutation, and so on.
This is different between the different variants.
So let's look at that again.
Evolutionary algorithms start by generating this initial collection.
That's the population.
From that we select parents, recombine and mutate.
And so we recombine some of the old members from the population,
produce offspring, and then we have, similar to this survival of the
fittest, some of those actually get into the old population and
replace some others.
The size of the population stays the same.
So we create new elements, replace the old elements, or some old
elements with new elements, and then have, hopefully, some progress.
And this, again, is that example here, what I just showed you.
The question, certainly, is how do we actually design those
chromosomes?
So we have some biological names here.
We talk about genotypes, about genes, about chromosomes, and things
like that.
But sometimes the way this is used, actually, is not completely
adequate with respect to the biological template, or the biological
original.
Nevertheless, we just use it in this way.
So every iteration, one iteration through that cycle here, is one
generation.
And the stopping criteria are different, maybe just the maximum number
of generation means you have a certain amount of effort, a certain
amount of computation time that you would like to spend, and that's
it, and you see how far you actually got.
Or you have some dynamic criterion.
You look at whether there is an improvement anymore.
If there is no improvement over a certain number of iterations, you
just stop.
Here is the algorithm in a simplified way.
You have your time variable counting the generations.
You have the selection.
You create a mating pool, M of T, from your population P of T, which
is built using some selection function S.
You perform a crossover on that mating pool, which can take many
different forms.
We will come back to that in a moment.
You perform mutation, and then we have some reproduction scheme where
we update the union of the old generation, not the old generation, the
old population, and this set M double prime of T, which is the mutated
offspring of the parents.
And this is iterated until the termination condition tells us to stop.
And so this is showing here again some subset of the population is
taken as parents.
We have the crossover, create some number of offspring, have the
mutations, and then create a new population of the same size as the
old population, but having new members.
The first thing we have to look at is how we actually represent our
individuals, because that can be very important with respect to the
possibilities we actually have to succeed in our optimization process.
So the individual can be just some string of elements.
Now, the string of elements can be just zeros, ones, some binary
string.
That would be the classical representation in genetic algorithms.
We know that we can represent everything just with binary values, but
for certain problems, it's not really the most natural representation.
So for example, for the traveling salesperson problem, it's much more
reasonable.
We know that it's a permutation problem.
You have to find the appropriate permutation of all the cities, which
leads to the length of the tour.
For that, it might be much more reasonable to have integer values.
We just number the cities from 1 to N, and then we find an adequate
permutation of those numbers from 1 to N.
And this is just a sequence of integer values.
We don't need binary values.
We could write down the binary values, but that doesn't really make
sense here.
Or we could have real values.
So you could also just code, also for the TSP, just code a sequence of
real values, and then you decide, like for example, in traveling
salesperson problem, usually you are at a certain city, and now you
would like to decide which is the next city that you take.
And you could have a sequence of real values.
You have to make N decisions.
And you could just take a number of real values, which decide on the
probability that you take the lowest or the city with the shortest
distance, or second shortest distance, or third shortest distance, or
something like that.
So you could modify certain heuristics by real values.
That way, modify a certain heuristic, greedy algorithm.
By modifying it, you have a larger way of actually exploring the
different possibilities.
So real values may have some definite value there, or some argument,
or you have other examples.
Just, you can think of other things.
I don't want to go into all these details.
So, you could also have other structures, not just lists of numbers,
binary, integer, or real values.
Maybe that you need a two-dimensional array.
Or maybe you would like to find a certain tree structure for a certain
problem.
Or that your problem is actually a certain tree structure.
Or maybe some graph.
And you have to find, for example, some way of interconnecting certain
nodes, such that the bisection width here is in some way maximized or
minimized, or whatever you would like to have.
You have to find certain ways of...
So you could think of different arrangements of graphs.
You could have, for example, the problem of drawing a graph.
And there, it doesn't really make sense.
If you have to draw a graph, and you would like to show how to place
the nodes on certain places in the area, in the two-dimensional plane,
does it make sense to have that as a linear array?
So there may be problem-depending structures that are reasonable to
use.
Or if you write a program, programs quite often have some graphical
structure.
And it does not make sense to write it as a linear array.
So you would like to use the structure that is inherent to the
solution that you actually have suggested.
And then you would like to perform also the other operations, cross
-over amputation on those structures.
So there are many different ways of representing a problem.
And you can imagine that depending on the way you actually represent a
problem, the evolutionary process, the optimization process, will be
heavily influenced.
So, yeah, you have a question?
So the question just was, it can be very difficult to find the most
appropriate representation.
Well, that's exactly true.
So this is one of the inherent problems in designing evolutionary
algorithms, that you have to find the most adequate representation.
And sometimes you find people who write something about the way you
can actually use evolutionary algorithms, or they test it and say it
didn't work.
And if you look at that, you find out, oh, they used the wrong
representation.
Had they chosen another representation, it might have been much more
beneficial.
So this is a problem where we don't really have a good standard
solution where you could say, this is this problem, do it like that.
There are some rules, some guidelines, but it is a difficult problem.
As I said, you can have, for example, represent a traveling
salesperson problem just as a list of cities.
You could also say, as I said, a list of real values, where these real
values in some way modify a heuristic algorithm for generating a
traveling salesperson problem.
That's a completely different representation of a problem leading to a
different fitness landscape.
And in this way, it influences the way significantly how we can
actually optimize those problems.
This is one of the most important parts to look at what is the best
genetic representation.
Sometimes you just have to experiment with that.
You can always try to do it in a direct way where you have your
genetic representation and this is exactly like your problem that you
actually want to have as sequence of cities.
And traveling salesperson problem can be almost the same or the
traveling salesperson tour, but it can also be very different and you
have to generate actually the solution that you are interested in from
the genotype.
That's what I have written here actually.
You can have the direct representation where genotype actually is the
phenotype.
Phenotype is the biological word for the appearance of a certain
genetically described artifact or entity.
So our genetic code, the DNA that we have, determines how we look
like.
And so for the traveling salesperson problem can be direct or it can
be just a list of parameters for some heuristic algorithm for
generating that traveling salesperson problem or for generating
certain scheduling or certain solutions to scheduling problems.
And the phenotype usually is what we use for evaluation.
So we have to generate a traveling salesperson tour in order to be
able to evaluate whether it has a length that is acceptable or not.
And so this can be done directly or sometimes we have to actually map
the genotype to the phenotype and then evaluate that phenotype and
this is usually called the fitness.
Although the fitness in a biological sense is the reproductive
strength of an individual, to what extent does actually an individual
or the genes of some individual appear in the successive generations?
So what is your reproduction strength?
What is the strength of your genetic code?
How often does it actually appear in the next generations of that
population?
And here we usually say that fitness is the quality of a certain
solution.
That's the quality with respect to our objective function and there we
actually deviate a little bit from the biological metaphor.
And then we have certain fitness mechanisms.
We select parents.
So we have to select appropriate individuals, some parents for
recombination.
Which do we choose?
So you can't look at the fitness values of the individuals.
You could say, okay, I just take the best.
But sometimes maybe that the combination of some not that good
performing individuals or not that well performing individuals might
lead to some combined genetic code which is much better than others
which were initially better in that population.
So it is not reasonable to do that in a deterministic way.
But usually we just determine some probability that tells us whether
we use or choose this individual or another one.
And this probability usually is determined by looking at the fitness
of an individual compared to the sum of all the fitness values.
So it's the relative fitness of an individual and this gives us the
probability that an individual is chosen.
Now, assume you have roulette.
It's called roulette wheel selection.
So you can have a roulette wheel where you have many individuals and
one individual has a very large fitness.
The other ones have a very small fitness.
And now the probability of that very well performing element would be
very large and it will be selected very often, again and again, which
means very strong dominance of one well performing individual.
So the selection probability here depends on the fitness value of the
individual relative to the sum of the fitness values of the rest of
the population.
And here you see that's a better drawing of that roulette wheel.
And what we have here is that we just select randomly just one element
and select the next one.
Just choose randomly some element and so some location on that
roulette wheel.
And certainly those having a larger sector have a larger probability
to get selected.
And so we have this roulette wheel selection scheme.
And so here you obviously have this dominance.
Like if you have a strong difference between the fitnesses of the
individual elements, so if you have a situation like this, that you
have one individual which has a high fitness and all the others have
very low fitness, then this one element will completely dominate all
the rest.
If you have a situation where they all are almost the same, then
there's no ranking really.
And it's rather an arbitrary process.
But still there might be some ranking that could be done.
And so you have to find out how to actually do that in an appropriate
way.
And so we have another scheme which is called the rank-based
selection.
If you use a rank-based selection, you just perform a ranking of all
the individuals.
So you just sort them with respect to their fitness values.
And then you can determine a selection probability depending on the
rank of the individual in the population.
And now you have something which is independent whether the actual
fitness value is very large relative to the others.
It's just the rank in the whole population which is determining the
probability.
And so in this way, every individual has some possibility to be
selected depending on its rank.
And you don't have these problems that the absolute differences might
determine actually the selection process.
And so now you can determine how you would like to assign that.
This, what is given here, is a typical function how to determine the
fitness or the probability for selection.
So you just take the rank, i, and then you have this value here which
leads to a situation where the probability that the worst individual
still has some probability to be selected.
So if i is the largest value, then no, that is zero.
So if i is the worst ranked individual, then you have n-1 over n-1.
That means 2 over n minus 2 over n is zero.
So the worst individual would not be selected and the best individual
would have the highest probability.
And so this is a way of having some kind of more homogeneous way of
actually selecting just based on the rank.
And the third way of doing this is to use the so-called tournament
selection.
Now what's a tournament?
A tournament is that you have a certain population of players and you
just select 2 or 3 or 4 and they have to compete with each other and
you take the winner of that tournament, of that selection.
And so a tournament usually selects a sample of 2 or 3 or 4, whatever
you would like to have, and then take the best out of that set.
So you compare those two, you have that tournament here, you have that
sample, you select the better one.
Or you could also have more values, you select the best one.
Or you could also have, again, some randomized selection there.
Usually it is a deterministic selection in that sample that you are
selecting.
So here you have actually some randomized selection of elements and
then take the best individual from that set of elements.
And in that way, you also have something which is similar to rank
-based selection.
The major advantage is, assume you just want to perform one crossover,
one reproduction process from two individuals.
In order to do that with roulette wheel selection or rank-based
selection, you have to sort all the elements or you have to compute
all the fitness values and then you can determine the positions and
you know the probability at which they are chosen.
If you take a tournament selection, you just grab, you just take a
sample of two or whatever number of elements you would like to take
and you only have to evaluate those.
You don't have to evaluate all the others.
Just that small sample and you take the best out of those.
You have a question?
Yes.
If we compare that to what I had on the previous slide.
So if you have here the best individual ranked one, what do we have
here?
That is, if I is one, we have here zero.
So the probability here of the best individual is two over N.
It's not that high.
And that's exactly the probability that we have if you select two
elements just randomly.
It's the same probability.
Yeah?
The roulette wheel selection has a preference for the best.
Definitely.
And the problem is that if you take roulette wheel selection, you get
biased towards the elements that have been better than others in the
first generations, which on the end might be not that good.
So if you have something looking like this, for example, maybe that
you are just there in the local optimum and you forget about all those
nice areas that you might have gone to if you would not have been
forced to take that individual.
So it's just something you have to... in some way you would like to
exploit the better individuals, but you have to explore the search
space.
That's why we take randomization.
In this example, why 10?
If N equals 10, the worst individual has zero because the worst
individual has rank 10 for N equals 10.
And then you have here N minus 1 over N times N minus 1, that's 2 over
N.
Here it's 2 over N.
N minus 1 cancels out.
Then you have 2 over N minus 2 over N, it's zero.
Here the best individual has rank 1.
The best individual rank 1 means that we have 2 times 0, so this is 0
in that case.
Then it's just 2 over N.
So it's one-fifth.
If N is 10, the probability for choosing the best individual would be
one -fifth.
The worst individual will never be chosen, but if you look at here the
tournament selection, the worst individual can never be chosen because
you always have two different individuals.
The worst individual will always lose compared to the others.
Yeah?
Okay, so this is tournament selection actually has many advantages
because it has not this bias towards the best performing solution.
It has rather uniform or more homogeneous representation of ranks, and
we don't have to evaluate all the elements if we would like to just
select two individuals, just perform one tournament between two
individuals.
We only have to evaluate those two.
We don't have to evaluate all the others.
The problem now is how we proceed from that, but we come to that.
Oh, one other thing, uniform selection.
Uniform selection would mean that they have all the same probability,
but that's then in no way directed by looking at the fitness.
So uniform selection is not really something which we would choose.
Now, how to produce new individuals?
There is recombination.
I said we create offspring.
So two individuals are selected, and then information from both is
combined in an adequate way to produce offspring.
There are many different operators for crossover, and the simplest one
I will show you.
So recombination again is something which can be done at random, so
there are always some randomized effects in there.
And then the next operation is mutation, just some arbitrary change in
the information we have in the genotype.
And the observation, the expectation is that we have an improvement by
recombining elements.
Now, this is definitely not guaranteed.
Maybe that you get something which is much worse, then this is just
discarded.
You only take those which perform better, or at least as well as the
parents.
And so this is another point that we have to look at, how we can
actually make sure that we will have an improvement process.
So let's first of all look at the recombination.
There are many different ways of recombination.
If we have two parents, then we select a cut-off point.
So this is a one-point crossover.
A cut-off point.
And then we could produce two offspring from that by just recombining.
We split the two parents at that position and recombine them, just
switch between the two parents, those elements.
Then we have two offspring which are combinations of the genetic code
of the parents.
Now you hope certainly that this code that you get then actually is a
valid representation of the problem.
Another thing that you have to consider when you decide for a coding
of the individual's representation should be done such that you can
actually get easily valid solutions.
Then we can also have two-point crossover.
Would mean that we have actually two selection, two cut-off points.
And then we would have here that this would be red and that part over
there should be blue.
Then with that, that would be two-point crossover where we just have
two points and we have this iteration or alternation between parts
from parent 1 and parent 2.
We could have k-point crossovers, but that is just increased.
And we can have a uniform crossover where for every position we would
have a random decision whether we take the information from parent 1
or parent 2.
So a random combination of genes from 1 and 2.
Now what are the essential differences?
If you assume or just assume that a certain part here, that part
maybe, is just coding relevant information, but if you would cut it
into two parts and recombine it with information from the parent,
maybe that this interesting block of information is lost.
So sometimes you would say it's good to have the chance to actually
take larger areas of my individuals into the next population, into the
offspring, and not have a complete reshuffle of the information.
Sometimes, for some problems, there is no actually neighboring
relationship between the different genes and then it doesn't really
make any difference whether you take them as a block or just have this
arbitrary uniform crossover.
So this is something which depends very much on the type of problem
you have, but it has been shown that two-point crossover actually has
benefits or has advantages over one-point crossover.
So usually, if you would say I take some standard approach, you would
take tournament selection and two-point crossover.
That usually has benefits.
And then the question is...
where is the mutation?
Mutation, certainly, there's no slide on that.
Mutation is just a random change applied to those chromosomes.
Usually, the mutation probability is determined such that every
individual will be modified at at least one position.
And for that, if this is the length of the individual, let's say L,
then the probability of mutation usually is one over L.
The one over the number of genes, genetic information in one
individual.
This is some rule of thumb, because this guarantees that the
expectation is that every individual will have at least one position
that is modified by mutation.
So rule of thumb would be, if you design an evolutionary algorithm,
certainly you could start with a simple direct representation of your
problem, take tournament selection, two-point crossover, and mutation
probability of one over length of the individuals.
And then the question is, which elements do you take over into the
next generation?
So there are two different schemes.
One is generational.
That means you have your old population.
You generate, so these are elements, so this is population P and size
of P is N.
And then you generate a new set that's our offspring, and it has the
same size.
So the offspring replaces the parent generation.
That's generational.
It means you lose everything that has been in the old population.
Parents are replaced with the two offspring.
And you could also say, okay, I combine that with elitism.
For example, the best solution survives.
The worst one is taken out, and then I have definitely the same number
of individuals as before, and I just make sure that I don't lose
information.
The alternative is to have something which is called steady state, and
there you would only select two parents, generate one or two children,
depending on what you have in your crossover operation, one or two,
and the child or these two children replace the worst individuals in
the population.
So in this way you will never deteriorate, because you can never get
worse information in your new population.
You can only improve.
And in this way you can have some process which will always lead to
improvement.
If you have generational situation, then it may be that you had a very
good solution, and all of a sudden that is replaced with new
offspring, and you run into a very bad region of your search space.
So usually what you would take is steady state.
But you can also generalize that, and you take something which is
called a comma approach, a comma selection, mu comma lambda.
This is usually associated with evolutionary strategies.
There you have a population size of mu, you select lambda children, so
you see you have both possibilities here, generational or steady
state.
And the best mu out of the lambda children form the next population.
So for this you would have to generate more or at least mu children.
You just take the best mu out of that number of children that you
have.
Then there is the mu plus lambda approach, where you take your
parent's population, the offspring's population, you combine both, and
you take the best mu out of the combined population.
That way you have something similar to steady state, where I said the
child replaces the worst individual in the population.
That's actually, again, different.
The child replaces the worst individual.
So you don't consider actually the fitness of the children, but take
out the worst individual of the population and put in the new
individual, the new offspring.
It might even be worse than the old worst element, but it certainly
can only survive if it will not be taken out in the next steady state
effect if it is considered to be the worst individual.
So here you always take the best mu out of the population that you
have generated, and this may be just the children or parent plus
children.
And so many different ways of selecting a new population.
That's essentially what I wanted to tell you about evolutionary
algorithms.
You can imagine that there are many different ways of actually
instantiating that for specific problems.
So, for example, assume you have two traveling salesperson tours and
one is leading from 1, 2, 3, 4, 5, 6, 7, 8, and the other one is going
from, let's say, from 5, 6, 7, 8, 1, 2, 3, 4.
If we perform a crossover, then we would combine those two would be
one new individual and the other two would be the next individual,
both covering only half of the cities, which doesn't make sense.
So for that, you need different types of crossover operations.
So if you have to determine the best possible permutation out of the
list of genomes or those genetic values, then you do it in a slightly
different way, but still adequately use the information from both
parents.
There are many different instances of that crossover operation, but I
didn't have time to actually go into the details of that.
This was just to show you the flavor of the evolutionary algorithms,
and if you would like to know more about that, you should go to the
course, for example, on nature-inspired optimization methods that is
taught by Pradyumna Shukla and Zanaz Mostagi.
Let's go back to the problem we have here with our load profiles.
We have the different possibilities for those devices, and we select
certain elements, and now we have to find out whether that is
adequate.
This is not really adequate, and now we might perform a certain local
optimization, because if you see here, there are several possibilities
to modify the amount of time that we actually need here for a certain
device.
So we could modify that.
So we could, for example, say, okay, we just...
So you see what I did here?
Oops, sorry.
We just select an earlier starting time, that is this here.
We could modify that.
Then it might fit.
As we did in the fridge, we could modify that slightly, or we could
let it run a little bit longer.
No, what's this?
Later start time.
This is down here.
So this was... just move it forward a little bit.
But it's not exactly what we had with the fridge, because with the
fridge, we could not really shift the complete amount of time where we
use power, but we could cut off earlier.
Or because we should never let the temperature rise over a certain
maximum value or go below a certain minimum value.
So there are restrictions to that.
But in between those temperatures, we could shift back and forth.
And then maybe we can just let a certain device run longer a little
bit.
Or we could actually let it run shorter.
Or we could increase the consumption.
So this was what we did here.
There are some devices where we can actually modify the power that
they actually need to run.
And so we can increase that.
Or maybe we can decrease the consumption.
And so those local changes are just used as far as possible in order
to try to improve the solution that is just suggested by that
algorithm.
And in that way, you have a local improvement and then you continue
your evolutionary algorithm.
So this is done by that pool or the balancing group manager, for
example, is selecting information from all those devices which are
relevant in the moment.
They tell their current preferences, their current plans, how they
would use power.
And then the balancing group manager would perform the optimization
process.
And then we have a new schedule.
The balancing group manager would tell all those devices at which time
they actually should use power, to what level.
And then we can do what is indicated here.
Then we can actually shift the load from some time here, from the
first time interval to some later time intervals.
And then certainly we have to make sure that all the other devices, or
that at those later times, actually the power is there that is needed
for the planned consumption.
So this has to be certainly balanced by controlling the appropriate
other devices.
So this is the idea that we shift balances to a later time and then
make sure that we have the balance again.
Oops, sorry.
And then this approach has been simulated in a certain setting where
we considered a virtual district of elements around 2000 refrigerators
and freezers.
So the individual fridge is only a small element.
But if you have a few thousand of them, it's a significant influence
on the power consumption.
And so this can be used.
All you have here, we assume, 84 combined heater power plants with
standard values for their power and heat capacities.
We simulated that over one day.
And so the average consumption here in that area was 56 kilowatt hours
and the average generation per hour was 54 kilowatt hours.
So a little bit, a small deficit actually.
Now you can look at how production and consumption actually are
balanced.
If you have something where all the consumption is done at a time
where you have no generation and at the time where you have generation
there's no consumption, you have complete imbalance.
Now you have no imbalance if it's completely balanced.
If generation and consumption is always the same value.
Now you can look at deviations and how your pool can respond to
deviations from a complete balance.
So there is a reference scenario for this area where you have an
imbalance without coordination of about 11.21%.
So there's still some imbalance there.
Imbalance always means that you need extra balancing power from
outside.
So if inside your district, this is our district, if here we have an
imbalance, so if you have a deficit or if you have a surplus, this has
to be compensated by exchange of power over the district borders.
We need extra balancing power for that.
And so this has to be looked at in an appropriate way.
You see the difference between consumption and production.
56 kWh is the average consumption per hour.
The production is just a little bit less.
So you have about 2% difference there.
So there's a small shortage of power.
And now certain typical situations have been tested.
How can you actually simulate that?
You start from some balanced situation, for example like this, where
everything here is balanced.
And then you have some disturbance.
You have increased demand at a certain period of time.
You have increased supply over a certain period of time.
And then again you have increased demand over a certain period of
time.
So this means extra demand, extra supply, extra demand.
And if you combine that, it means that your power schedule that looked
like this before now looks like this.
You have here this increased demand.
You need extra power here.
There you have surplus of power.
The demand is not large enough here.
And there again you have a shortage of power.
Now the question is how can we actually compensate those deviations by
just rescheduling the devices in that region, use their potential
degrees of freedom, shifting the load backwards and forwards such that
we can actually compensate those deviations, those imbalances.
And this has been done, like this is just a table which I actually
cited from the dissertation from Andreas Kamper.
That's from his dissertation.
So he looked at different situations, different sizes of the
imbalance.
So 10, 20, 30, 40, 50, 60 kilowatt, which lasted over a certain amount
of time.
So here you have your daily situation.
And then you have a certain deviation at that point in time.
Then there again, there again, there again, there again.
Regular pattern, for example, and this is, for example, 30 minutes.
And then again, then no imbalance, again 30 minutes and so on.
So some regular or maybe also some irregular patterns.
You will see in the next slides that different patterns have been
tested.
And so here you see that the deviations that you get without
coordination, if you just let the system run and you have this extra
demand in a situation that had these average of 54, 56 kilowatt hours
consumption per hour.
If you look at that, you have a difference, like in parentheses, this
is the imbalance without coordination.
And this here is the imbalance that remains after you have optimized
all your devices.
You can reduce the imbalance, but still there is some remaining
imbalance.
So the reference scenario was that you have something like, even if
you just look at the normal situation, you had an imbalance of
coordinated, of almost 5%.
If you just have a little bit of extra disturbance here, like even if
it's for 30 minutes, 60 minutes, 90 minutes, this does not actually
disturb the system too much.
If you have a high imbalance for quite a bit of time, like for 30
minutes, 60 minutes, actually here, the longer the imbalance is there,
the better you can actually compensate that.
This is interesting, that you can actually have here, or get this
result, that if you have a long time of imbalance, you can here shift
more appliances appropriately.
So if I look at that in, oops, it's not shown here, here I just have
this table, a few slides on, we see the effect of a slightly modified
scheme.
Something which is not satisfying is that we still have quite some
significant imbalance, which is still visible here.
And the idea was to improve that.
Yeah?
Yes.
With coordination is always the first one.
In parentheses, always without the coordination.
Yeah.
I guess, so you see that we had these combined heat and power plants,
which are also there.
And I guess that you can use them in an adequate way to compensate for
that.
I cannot tell you exactly how that was achieved.
This is just the result of that simulation where exactly those types
of degrees of freedom were assumed as I have shown you before, that
fridges have this capability of shifting something backwards or
forwards within those time frames where they have to cool something
down.
And the combined heat and power plants have some possibility to switch
back and forth.
They have certain restrictions with respect to the maximum amount of
heat they can produce.
So there's also some limit which is given by the temperature of the
hot water tank.
And so these limits were all used and it led to those results.
We could look into the dissertation of Andreas Kamper and find out how
that was actually achieved.
But here you just have to believe that that is the adequate result.
Now, the problem is that all these optimizations that were done were
done using optimization by the balancing group manager.
The balancing group manager was always getting all the information,
performing the optimization and then telling all the others what to
do.
And now the idea is to actually modify that and get something which
can be done in a more decentralized way.
And here the major idea is to create something which you call an elite
group.
And if I look at my watch, the time for the first lecture is over and
we make a break of 15 minutes.
Thank you.