Liz Williams.
Worldsoul.
Prime Books. 2012
For Mercy Fane, the day starts as any other for a Worldsoul Librarian:
choosing a weapon to fight the dangers escaping from the books.
What emerges will involve not only her, but also a hidden descendent of old Norse legends,
a demon from Hell itself, and an Alchemist from the Eastern quarter,
in a desperate fight against those who would destroy Worldsoul.
There is a rich vein of fantasy that has heroic Librarians
fighting against the dangers that can leak out of Old Books.
I understand the desire for heroic librarians;
I’m not so sure that having the books be the danger is the best idea
in this age of anti-intellectual post-truth.
However, here we have another hero-Librarian fighting off the demons.
Worldsoul is a beautifully drawn, rich and detailed world,
with a complex plot drawing on a range of old-Earth mythologies.
In a lesser author’s hands, the range of characters, locales,
and mythologies might have resulted in fragmentation;
here Williams draws them all together in a fine tapestry,
with a powerful cumulative building of the plot details.
The plot itself comes to a conclusion, but the ending provides the potential for a sequel.
There are hints on the web that such a sequel is “projected”,
but it does not seem to exist yet.
I would welcome another tale in this universe.
For all my book reviews, see
my main website.
a memory less ephemeral
random stuff that caught my fancy that I would otherwise forget
Sunday, 15 October 2017
Saturday, 14 October 2017
multi-objective optimisation II
In a previous post, I described what a Pareto front is, and Deb et al (2000)’s algorithm for finding it. We have the first element we need for a multi-objective optimisation algorithm. There is one more subtlety first, though.
We want to get a good estimate of the whole Pareto front, not just a few points on it. So we want the points we find to be well spread out across the front. Deb et al define the crowding distance: we prefer less crowded to more crowded points, as the densely crowded ones are not giving us much extra information about the front. Their algorithm is:
Here, I is the set of points, and I[i].m is the value of the mth objective function of the ith individual in I. We can code this up in python as follows (with I being a list of points in a particular front):
The python then does one more thing than the Deb et al algorithm. It uses the distances calculated to sort the original list of individuals into reverse distance order (high distance isolated points near the the front, low distance crowded points towards the end) and returns that sorted list.
Then we can sort the list of fronts in the obvious way:
Here are some results, for the Kursawe function, and for a population size of 100 (click to get a larger view).
So that’s it! Deb et al’s multi-objective optimisation algorithm, in python.
We want to get a good estimate of the whole Pareto front, not just a few points on it. So we want the points we find to be well spread out across the front. Deb et al define the crowding distance: we prefer less crowded to more crowded points, as the densely crowded ones are not giving us much extra information about the front. Their algorithm is:
Here, I is the set of points, and I[i].m is the value of the mth objective function of the ith individual in I. We can code this up in python as follows (with I being a list of points in a particular front):
def crowding_distance_assignment_single_front(pfront): # pfront = list of individuals, dictionary { 'state':s, 'fitness':(f1, ... fm) } inf = 1000000 # "infinity" dist = [0] * len(pfront) # list of distances, I_distance m = len(pfront[0]['fitness']) # no of objectives (= size of 'fitness' tuple) for mi in range(m): # sifront = [(i, pfront[i]), ...] sorted on mi-th fitness values of pfront # sifront[j][0] = original index i of item in pfront list # sifront[j][1]['fitness'][mi] = mi-th fitness value of jth sorted individual sifront = sorted(enumerate(pfront), key=lambda x:x[1]['fitness'][mi]) dist[sifront[0][0]] += inf # first boundary item in list dist[sifront[-1][0]] += inf # last boundary item in list for i in range(1,len(sifront)-1): dist[sifront[i][0]] += sifront[i+1][1]['fitness'][mi] \ - sifront[i-1][1]['fitness'][mi] # sort pfront into reverse distance order, using distance list dist, pfront = (list(t) for t in zip(*sorted(zip(dist,pfront), key=lambda x:x[0], reverse=True))) return(pfront)The algorithm works by sorting the list of individuals in order of their fitness value for objective mi. The distance value of each point is the sum of the distances to its two neighbouring points: crowded points will have low distances, so low distances are bad. The first and last points in the list are given a very high (good) value. This is repeated for each objective dimension, adding up the distance measures.
The python then does one more thing than the Deb et al algorithm. It uses the distances calculated to sort the original list of individuals into reverse distance order (high distance isolated points near the the front, low distance crowded points towards the end) and returns that sorted list.
Then we can sort the list of fronts in the obvious way:
def crowding_distance_assignment(pfrontlist): for i, pfront in enumerate(pfrontlist): pfrontlist[i] = crowding_distance_assignment_single_front(pfront) return(pfrontlist)Now we have enough to make a multi-objective search algorithm:
Np = 100 # parent population size Nq = 100 # no of children Ngen = 250 # no of generations Nstate = 3 # size of individual state parents = init_popl(Np,Nstate) children = make_children(parents, Nq) for _ in range(Ngen): popl = parents + children # construct the list of fronts from the population (previous post) pfrontlist = fast_nondominated_sort(popl) # sort each front into least crowded (highest distance) order pfrontlist = crowding_distance_assignment(pfrontlist) # new parents become the best of the previous popl of parents + children parents = [item for pfront in pfrontlist for item in pfront][:Np] # make new children from those parents # note that parents are sorted in fitness order children = make_children(parents, Nq)We need to define init_popl() to build some initial (usually random) population.
import random
def init_popl(n,nstate):
# return list of n individuals, each with nstate state vars, each in -1..1
pop = []
for _ in range(n):
state = tuple([random.uniform(-1,1.) for i in range(nstate)])
pop += [{'state': state, 'fitness': fitness(state)}]
return pop
Here I have simply hardcoded in an initial range of +/-1, because I am demonstrating this with the equally hard-coded Kursawe function objectives:import math def fitness(state): # Kursawe function x1,x2 = state f1 = -10*math.exp(-0.2*math.sqrt(x1**2+x2**2)) \ - 10*math.exp(-0.2*math.sqrt(x2**2+x3**2)) f2 = abs(x1)**0.8+5.*math.sin(x1**3) \ + abs(x2)**0.8+5.*math.sin(x2**3) \ + abs(x3)**0.8+5.*math.sin(x3**3) return(f1,f2)Now all that’s left is to define make_children(), which breeds the next generation. Deb et al simply say “Binary tournament selection, recombination, and mutation operators are used to create a child population”. So, for the sake of demonstration, let’s do the simplest possible thing here: binary tournament with a fixed mutation of the three component state, and no recombination:
def make_children(parents, nq): # parents = list of items in fitness order, fittest first # (except on v first call) # nq = no of children to make # tournament selection + mutation np = len(parents) children = [] for _ in range(nq): # binary tournament: chose two parents randomly p12 = random.sample(range(np),2) # tournament winner = lower number, because sorted p = parents[min(p12)] s = mutate(p['state']) children += [ {'state': s, 'fitness': fitness(s)} ] return children def mutate(state): x,y,z = state return (x+random.uniform(-0.1,0.1), y+random.uniform(-0.1,0.1), z+random.uniform(-0.1,0.1))Clearly, init_popl(), fitness(), make_children(), and mutate() should be modified into general purpose code, but that’s not the point of this post.
Here are some results, for the Kursawe function, and for a population size of 100 (click to get a larger view).
After 250 generations. The Pareto front is fully defined and evenly filled; the corresponding state values are well clustered. |
After 250 generations with no call of the crowding_distance_assignment() function. The Pareto front is less well defined, and less evenly populated. |
Reference
Deb, Kalyanmoy; Agrawal, Samir; Pratap, Amrit; Meyarivan, T. (2000) A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. In Parallel Problem Solving from Nature, PPSN VI. LNCS 1917:849–858. Springer. doi:10.1007/3-540-45356-3_83
Friday, 13 October 2017
book review: Uprooted
Labels:
books,
review,
science fiction
Naomi Novik.
Uprooted.
Pan. 2015
The wizard known as Dragon takes a village maiden every ten years, to serve him in his castle, while he keeps all the villages in the valley safe from the darkness of The Wood. This year, to everyone’s surprise, he chooses the awkward Agnieszka. What she didn’t know is that she has magic. And her magic may be the key to unlocking the secret of The Wood. If anyone will take her seriously.
This is a great fantasy novel. Agnieszka has to learn she has magic, then learn how to use it, then learn what it needs to be used on. This sounds standard enough stuff, especially with the evil in the dark forest, and the Dragon wizard, and the king’s son, and the missing queen, and, and… Yet the plot keeps branching off in surprising directions, growing in unexpected ways, and these standard fantasy tropes are made to bear unexpected fruit.
And the plot really races along. At one point I was musing that there had already been enough material and plot twists for one or even two volumes of the typical “fat book” fantasy trilogy, but I was barely half way through! This does not compromise the richness of the plot: Uprooted is exciting and satisfying read.
For all my book reviews, see my main website.
Uprooted.
Pan. 2015
The wizard known as Dragon takes a village maiden every ten years, to serve him in his castle, while he keeps all the villages in the valley safe from the darkness of The Wood. This year, to everyone’s surprise, he chooses the awkward Agnieszka. What she didn’t know is that she has magic. And her magic may be the key to unlocking the secret of The Wood. If anyone will take her seriously.
This is a great fantasy novel. Agnieszka has to learn she has magic, then learn how to use it, then learn what it needs to be used on. This sounds standard enough stuff, especially with the evil in the dark forest, and the Dragon wizard, and the king’s son, and the missing queen, and, and… Yet the plot keeps branching off in surprising directions, growing in unexpected ways, and these standard fantasy tropes are made to bear unexpected fruit.
And the plot really races along. At one point I was musing that there had already been enough material and plot twists for one or even two volumes of the typical “fat book” fantasy trilogy, but I was barely half way through! This does not compromise the richness of the plot: Uprooted is exciting and satisfying read.
For all my book reviews, see my main website.
Wednesday, 11 October 2017
multi-objective optimisation I
There are lots of optimisation algorithms around: I’ve used simulated annealing and evolutionary algorithms, to name but two. However, I’ve only ever used them to optimise a single value. But real problems often have multiple objectives to satisfy simultaneously: time, price, and quality is a traditional triple. However, multiple objectives are often in conflict, and so it is not possible to optimise them all simultaneously: there are tradeoffs. “Pick any two of three” is the stated tradeoff for time, price, and quality; more nuanced tradeoffs are available.
One common technique is simply to add the various objective values together, with some weight for each, to reduce the problem to a single optimisation. But which weights? Different weights imply different tradeoffs.
So the next step is a full multi-objective optimisation system. To see what is going on, the crucial concept of dominated solution needs to be understood.
Let’s assume that a candidate solution s has objective values (f_{1}, f_{2}, ..., f_{n}). And let’s assume we want to minimise each of those objectives (the maximisation case is similar, mutatis mutandis). Then solution s_{1} dominates solution s_{2} if every one of its objective values is less than the corresponding value for s_{2}. If on the other hand, s2 is better in all its objectives than s_{1}, then s_{2} dominates s_{1}. And in the case when neither dominates the other, these solutions are non-dominated. The figure below illustrates these concepts.
When we don’t have all candidate solutions to hand, maybe just a sample of solutions, we need an optimisation algorithm to find those candidates close to the actual Pareto front, and to use them to find even better ones.
But first, we need to calculate the points on the Pareto front of a given population, that is, all the candidate solutions that are not dominated by any other solutions (the green points in the figure above). The obvious algorithm (for each candidate solution, test it against all other solutions for all objectives) is rather inefficient, being O(MN^{2}), where M is the number of objectives, and N is the number of solutions to test. Deb et al (2000) give a more efficient algorithm:
We can code this up in python as follows (with comments showing how it relates to the algorithm above):
The multiple front calculation is as follows:
In a later post, I will go through the rest of the Deb et al (2000) algorithm, and show how they incorporate this front-finding into a full-blown multi-objective optimiser.
One common technique is simply to add the various objective values together, with some weight for each, to reduce the problem to a single optimisation. But which weights? Different weights imply different tradeoffs.
So the next step is a full multi-objective optimisation system. To see what is going on, the crucial concept of dominated solution needs to be understood.
Let’s assume that a candidate solution s has objective values (f_{1}, f_{2}, ..., f_{n}). And let’s assume we want to minimise each of those objectives (the maximisation case is similar, mutatis mutandis). Then solution s_{1} dominates solution s_{2} if every one of its objective values is less than the corresponding value for s_{2}. If on the other hand, s2 is better in all its objectives than s_{1}, then s_{2} dominates s_{1}. And in the case when neither dominates the other, these solutions are non-dominated. The figure below illustrates these concepts.
def dominates_min(a,b): # for minimisation problems # a and b are nD tuples of the respective n objective values # a dominates b if a.x < b.x and a.y < b.y and ... return all([(a < b) for a, b in zip(a,b)])
How this works: Let the tuples by (ax, ay, az) and (bx, by, bz). Then zipping them together gives the list of tuples [(ax,bx),(ay,by),(az,bz)]. The set comprehension gives a list of booleans, True or False depending if the respective ai<bi or not. Then the all function tests whether all the values are True.In a complete collection of candidate solutions, the ones not dominated by any other solution form the Pareto front. These are the best possible solutions: no other candidate performs better in all objectives. The front describes the possible tradeoffs: values along the front represent different tradeoffs.
When we don’t have all candidate solutions to hand, maybe just a sample of solutions, we need an optimisation algorithm to find those candidates close to the actual Pareto front, and to use them to find even better ones.
But first, we need to calculate the points on the Pareto front of a given population, that is, all the candidate solutions that are not dominated by any other solutions (the green points in the figure above). The obvious algorithm (for each candidate solution, test it against all other solutions for all objectives) is rather inefficient, being O(MN^{2}), where M is the number of objectives, and N is the number of solutions to test. Deb et al (2000) give a more efficient algorithm:
We can code this up in python as follows (with comments showing how it relates to the algorithm above):
def fast_nondominated_sort_single_front(pop): # pop = list of individuals # individual of form { 'state': (s1,s2,s3,...), 'fitness':(f1,f2,f3,...) } # pfront = list of individuals on the calculated "pareto front" pfront = [ pop[0] ] # P' = {1} for pi,p in enumerate(pop): # for each p in P and p notin P' if pi == 0 : continue # (so not the first element) pfront = pfront + [ p ] # P' = P' cup {p} # make a copy to iterate over, because pfront is being modified; # don't need the last item, which is p (makes q neq p below True) pfrontcopy = pfront[:-1] pf = p['fitness'] for qi,q in enumerate(pfrontcopy): # for each q in P' and q neq p qf = q['fitness'] if dominates_min(pf,qf): # if p dom q pfront.remove(q) # then P' = P' \ {q} elif dominates_min(qf,pf): # else if q dom p del pfront[-1] # then P' = P' \ {p} break # don't have to check any more qs as p already gone return(pfront)Once we have the front, we could remove it from the population, and claculate the next front, and so on. This is useful in an optimisation algorithm, to find less fit (not on the current best front) but still possibly good solutions, for use in building even better ones.
The multiple front calculation is as follows:
def fast_nondominated_sort(pop): # find a list of ever decreasing fronts # pop = list of individuals # pfrontlist = list of fronts = list of lists of individuals popcopy = pop[:] pfrontlist = [] while popcopy: pfront = fast_nondominated_sort_single_front(popcopy) pfrontlist += [pfront] # remove the found pfront from the pop popcopy = [ ind for ind in popcopy if ind not in pfront ] # check that no-one has been lost assert len(pop) == len([item for pfront in pfrontlist for item in pfront]) return(pfrontlist)Given some population of candidate solutions, we can plot out the relevant fronts so calculated (plotting code always seems much more complicated than the actual algorithms!):
import matplotlib.pyplot as plt def plot_fronts(pfrontlist): # pfrontlist = list of fronts; each front is a list of individuals fig = plt.figure() ax1 = fig.add_subplot(111) # one colour per front colors = matplotlib.cm.rainbow(np.linspace(0, 1, len(pfrontlist))) # iterate backwards, to draw better fronts on top of less good ones for i in range(len(pfrontlist)-1, -1, -1) : pfront = pfrontlist[i] # sort members of front in order of fitness; draw a line along the front data = sorted([ pf['fitness'] for pf in pfront ]) xs = [ i[0] for i in data ] ys = [ i[1] for i in data ] ax11.plot(xs, ys, ':o', color=colors[i], mew=0) plt.show()This gives a plot like:
A sequence of fronts, found by finding the Pareto front of a population of candidate solutions, removing it from the population, finding the front of the remaining candidates, and so on. |
In a later post, I will go through the rest of the Deb et al (2000) algorithm, and show how they incorporate this front-finding into a full-blown multi-objective optimiser.
Reference
Deb, Kalyanmoy; Agrawal, Samir; Pratap, Amrit; Meyarivan, T. (2000) A Fast Elitist Non-dominated Sorting Genetic Algorithm for Multi-objective Optimization: NSGA-II. In Parallel Problem Solving from Nature, PPSN VI. LNCS 1917:849–858. Springer. doi:10.1007/3-540-45356-3_83
Tuesday, 10 October 2017
production-quality spam
What new spam is this?
Here’s an email I’ve just received (needless to say, I have not designed a tool called BalbiEtAl2017, which sounds like a BibTeX tag).
I haven’t clicked on the link, because, email link, duh!
For all my social networking posts, see my Google+ page
Here’s an email I’ve just received (needless to say, I have not designed a tool called BalbiEtAl2017, which sounds like a BibTeX tag).
I haven’t clicked on the link, because, email link, duh!
For all my social networking posts, see my Google+ page
Monday, 9 October 2017
Brexit: the Athenian expedition against Syracuse
Labels:
politics
Repeating history, one disaster at a time.
[via Danny Yee's blog]
For all my social networking posts, see my Google+ page
Read the reasoning...None of the above. I’d say the Athenian expedition against Syracuse.— Chr s Kendall ðŸ‡ªðŸ‡º (@ottocrat) October 9, 2017
[via Danny Yee's blog]
For all my social networking posts, see my Google+ page
Sunday, 8 October 2017
phenomenon-based learning
Finland ahead of the education game yet again.
[via Danny Yee’s blog]
For all my social networking posts, see my Google+ page
Finland Will Become the First Country in the World to Get Rid of All School Subjects
[assume there’s an interesting snippet quoted from the article here – there isn’t, because the article is “protected”, by someone who doesn’t understand how the Web works]
[via Danny Yee’s blog]
For all my social networking posts, see my Google+ page
Subscribe to:
Posts (Atom)