Esgian Hackathon rules
Hackathon rules:
- Teams of 2 developers.
- At the start a technique and input files are provided.
- Spend any time you want reading on the subject, but remember that you need to deliver a working prototype at the end of the hackathon. No working prototype means disqualification.
- Any programming language can be used.
- No outside libraries are allowed other than standard ones for the language.
- Don't copy an existing solution, that would defeat the purpose.
- Plan and distribute tasks within your team any way you want.
- Communicate any way you want.
- At the end of the hackathon, all prototypes will compete on my laptop for fairness, so make sure they're distributable (don't run on a server).
- The prototypes will have a set amount of time to run and the best solution will need to be presented at the end of the time slot in a certain format.
- I'll load the solutions in an application to judge them.
- Only 1 run per prototype.
- The best solution by the end of the run is the overall winner.
- The most elegant code/solution will be the runner up (so write good code).
The problem:
- Traveling salesman problem: n cities on a map, visit all cities only once, then go back to the first city, shortest route wins.
- Legs of the routes can cross (but you can't visit a city twice, except the first city which is also the last).
- The map will be 2D and the distances will be straight lines (no spheric or hypersperic geometry nonsense).
- Typically, the search space is #cities!. If you have 500 cities, that's a number of combinations that has 1135 digits. And it grows exponentially. You quickly reach a point where you can't possibly look at all the solutions to find the best one.
- That's where you need techniques that aren't dependant on the number of possible solutions.
- There are many ways of looking at the problem. GAs are a good and fairly simple solution:
- They're typically used when your search space is too large to explore or you don't know how to compute the solution because the problem is too complex.
- But if you know how to evaluate how good a solution is when you see one, a GA can find an *adequate* solution given your constraints. Not necessarily the best, but the bext is not always needed.
- No matter the complexity of the problem, the GAs have a constant complexity (that's their best advantage).
- They're often used for complex scheduling problems.
- University classes for example, with lots of students, lots of lecturers, lots of courses, multiple campuses, constraints in terms of time wasted/gaps in the day/travel, etc. (I have worked on one of those problems at my university).
- In my spare time I've used it to create a telescope scheduler for supernova verification taking into account altitude, visibility, and optimising gaps and downtime.
- For us, imagine scheduling vessel movements to make them more efficient, with thousands of vessels, thousands of ports, port spec constraints, many possible journeys between ports, cargo to move around with its constraints (e.g. food), emissions restrictions, cost, fuel usage.
- For the hackathon, you'll be given a map grid with cities randomly placed in a file.
- You can start and end from any city, but you need to end on the city where you started (your solution should be cyclic).
- The grid for testing might not be the same size as the final competition grid, the number of cities might be different, so be flexible in your implementation. Hint: let your data be driven by the input file.
- The input data will be represented as a text file of cities and coordinates. The final run will have the same input format but different amounts.
- The end result of your prototype should be a text file in the same format as the input file.
- Your application needs to stop and record its best solution when a key is pressed, even if it's not finished.
- Distances between cities are calculated as follows:
For 2 cities with coordinates x1,y1 and x2,y2:
private static double GetDistance(double x1, double y1, double x2, double y2)
{
return Math.Sqrt(Math.Pow((x2 - x1), 2) + Math.Pow((y2 - y1), 2));
}
What you'll need:
- Learn about GAs very fast.
- Plan your experiments based on your learning (GAs have lots of algorithms). I was introduced to GA at the university during my MSc and I wrote a 150 page report on algorithms and experiments to justify my choices.
- Plan your work for a very tight deadline.
- Design your solution and gamble on the way to solve the problem from the start (not much time for course adjustments along the way).
- Design your population and generation strategy.
- Look at the problem to decide how to represent your genes and chromosomes, and how to start your population 0.
- Decide population size.
- Decide on generation or individual evolution strategy (you can run GAs at the population or individual level, though it's usually population).
- Decide or experiment on mutation strategy.
- Gaussian?
- Swap?
- Uniform?
- Decide or experiment on mutation speed.
- Slow or fast?
- Decide your crossover strategy and implementation.
- 1 point?
- Multiple points?
- Uniform?
- k-point?
- Shuffle?
- etc.
- Multiple or single population?
- Isolated islands?
- Crosspolinisation?
- Single population?
- Some kind of hybrid?
- Design your fitness function.
- How do you know if a chromosome is valid?
- How do you know a chromosome is better than an other?
- How do you calculate the fitness of a chromosome as a solution to the problem?
- Decide on your environment pressure and selection function.
- Random?
- Elitism?
- Tournament?
- Stochastic?
- Truncation?
- etc.
- How do you detect false plateaus and hallucinations?
- GAs are very easily parallelisable at several levels (hint).
- Separate responsibilities in your team to parallelalise your tasks (think about your strengths).
- To know your score, run the evaluation application (SolutionEvaluator.exe) on your solution file (result.txt) with as parameter your team's name. Team scores are displayed in real time here: https://esgianhackathon.com/
Starting point:
- https://en.wikipedia.org/wiki/Genetic_algorithm
Back