xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

F#和C#代写-CAB402-Assignment 1

时间：2021-04-17

CAB402 Programming Paradigms

Assignment 1

Due: 23rd April 2021

Worth: 30%

The purpose of this assignment is to develop your functional programming skills by implementing a non-trivial application using

F#. The principal focus will be on learning to program in a “pure” functional style – i.e., without making use of any mutable state.

In order to contrast this pure functional style of programming with the more traditional imperative (impure) and object-oriented

paradigms, you will develop two separate implementations of the Genetic Algorithm library:

1. A pure functional implementation using F#

2. An object-oriented C# implementation

Required Software

1. Latest version of Visual Studio 2019 (with .NET desktop development and .NET 5.0)

Genetic Algorithms

For many so-called Combinatorial Problems, there exist an exponential number of possible solutions. For sufficiently large

problems it therefore becomes prohibitively time consuming to perform a brute force analysis of every possible solution. We must

resort to some form of heuristic algorithm that aims to find a good solution, but not necessarily the best possible solution. One

such class of heuristic algorithms is Genetic algorithms which are based on the process of evolution and natural selection as occurs

in the wild. We start with some population of individuals, those individuals mate to produce offspring. This mating process creates

children that have some combination of genes derived from their parents. During this reproductive process, some genes might

also mutate (i.e., accidently change at random). Such random mutations are generally harmful to the child, but occasionally they

might result in a fitter mutant offspring. Natural selection means that fitter individuals are more likely to mate and pass on their

genetic material to the next generation, so over time, the population as a whole tends to get fitter.

In a genetic algorithm, each individual in the population represents a particular proposed solution to a specific combinatorial

problem. So, to use a genetic algorithm to solve a combinatorial problem we must first decide how we will encode a proposed

problem solution as a sequence of genes. Each gene will represent some particular aspect of the solution. We can use whatever

data type we like to represent each gene. For example, we could use binary bits, integers, real numbers, characters, etc. The choice

will depend on the particular problem we are trying to solve.

If natural selection involves “survival of the fittest”, we need to provide a means for determining which individuals are fitter or

better than others. We need to provide a fitness function that takes a sequence of genes as input and returns a numeric fitness

value (where higher means better). The fitness function depends on what aspect of the problem we are trying to optimize. If we

want to optimize for some different property, then we just need to change the fitness function used and the evolutionary process

will then tend to find better and better solutions according to that fitness criteria.

In this assignment we are going to use Genetic Algorithms to solve two different combinatorial problems:

1. Travelling Salesperson Problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem)

The first is the Travelling Salesperson Problem (TSP), a well-known NP-hard combinatorial problem. Given a set of cities at specific

locations, the challenge is for the salesperson to visit each city precisely once and then return to where they started, while

travelling the least total distance. Visiting the cities in different orders will result in different total distances, so when encoding a

particular solution to the TSP problem as a sequence of genes, it is natural to use a sequence of integers representing the order

in which the cities will be visited. For example, the sequence [2,4,3,1,5] means that we would start at city 2, then travel to city 4,

then to city 3 and so on before eventually returning to city 2. Given a particular order in which cities will be visited we can compute

the total distance travelled, so the fitness function is based on total distance travelled, however, since we want to minimize the

total distance travelled, we actually use the negative of the total distance travelled as our fitness value, since we want a higher

fitness to correspond to a better solution.

2. The Resource Constrained Scheduling Problem (RCSP) (https://en.wikipedia.org/wiki/Genetic_algorithm_scheduling)

The resource constrained scheduling problem (RCSP) is another well known and important combinatorial problem. We are given

a set of jobs (or projects) that need to be completed. There are also a finite number of various types of resources that are needed

to help complete the jobs. Each job requires a particular number of these various resources. For example, job 1 may require 2

resources of type A and 1 resource of type B, while job 2 might require just 1 resource of type A. Each job also has a specific

duration. The resources used by a job need to be available for the entire duration of that job, i.e., they can not be used by any

other job during that time period. The resources are renewable, meaning that once we are finished using them for one job, we

can use them again for some other job. We are also given an objective function that we are trying to optimize. Often, we are just

trying to minimize the total duration required to complete all jobs. A solution to the RCSP involves determining a start time for

each of the jobs and an allocation of resources.

One popular method for creating such a solution is the Serial Schedule Generation Scheme. This algorithm involves scheduling

each of the jobs, one by one in a particular order. For each job we seek to determine the earliest possible time that the job could

be feasibly scheduled given the jobs that have already been scheduled. When we say feasibly scheduled, we mean that for the

entire duration of that job (from start time to start time plus the job duration), that we can allocate the required resources for

that job such that those allocated resources are not being used by any of the other jobs during that time period. If we change the

order in which we schedule the jobs, then the resulting schedule will change and possibly have a better or worse total duration

required to complete all jobs.

So, in searching for the best possible schedule, rather than considering every possible schedule, we instead just need to determine

the order in which we should schedule the jobs, because a given scheduling order leads deterministically to a specific schedule.

Solving a RCSP problem using a genetic algorithm is therefore very similar to solving a TSP problem. In both cases we are seeking

an ordering (or permutation). In one case the order in which cities should be visited, and in the other the order in which we should

serially schedule the jobs. So, we use the same genetic representation as for TSP, a sequence of integers (which must always be a

permutation). The only difference is the fitness function. In the case of the RCSP problem, we take the job order provided by a

particular individual’s genes and use it to conduct a serial schedule generation. From that we can determine the finish time of the

latest job and return the negative of that time value (since a shorter total duration is considered better).

During serial schedule generation, determining the earliest possible start time for each event can be computationally expensive

as it may involve considering many possible start times before we eventually find one that works. In order to make this algorithm

more efficient, we exploit the following observation: The earliest possible start time for a job is always going to be either time 0

(if it can be started immediately), or it will be the precise finish time of some other job that has already been scheduled. So, rather

than testing every possible potential start time, we only need to consider either 0 or the distinct finish times of jobs that have

already been scheduled. But we can leverage this idea even further. In determining whether some job can start at say time t0

(where t0 is either 0 or one of the previous finish time), we then need to ensure that the resources that we are proposing to

allocate to this job are available for the entire duration of that job (i.e., times t such t0 <= t < t0 + duration). However, based on

the above idea, we do not actually need to check at every time point between t0 and t0+duration. We need only check at the time

points within that period which also happen to be a finish time of one of the previous jobs – because it is only at those time points

that resource usage changes. So, we can save the time checking at all the other time points within that period.

If job 1 requires one resource of type A and there are a total of 3 resources of type A, then in developing a schedule we need to

decide not only the start time of job 1, but also which resource of type A we will allocate to it. Otherwise, it would be difficult to

ensure that particular resource instance will be able to be used solely by job 1 for its entire duration. We therefore number each

resource instance from 0 up to N-1 where N is the finite number of resources of that type available.

Athletics Event Scheduling

The resource constrained scheduling problem is applicable to many real-world problems, from scheduling exams or staff rosters

or factory manufacturing schedules. In this assignment we are going to consider a real-world problem of scheduling the events for

a junior athletics competition. We are given a list of events that each age group of athletes will compete in during the competition.

For example:

U15-17G Javelin

U8B 70m Sprint

U13-14B Long Jump

U15-17G 700m Walk

etc …

Each event requires two resources. It requires the group of athletes in that age group and it requires a suitable location to conduct

the event. Each different type of event requires a different type of location. For example, the 70m Sprint and the 700m Walk both

require a running track, while the Long Jump event require a sand pit. For a given competition arena, there are a fixed set of

locations which are available for each type of event. For example, there may be 4 sand pits, but only 1 running track. When

scheduling an athletics event (using serial schedule generation) we must ensure that both required “resources” are available for

the entire duration of that event: the group of athletes in that age group need to be available and the location that will be allocated

to that event, e.g., sand pit number 2, needs to be available. Each event will have a fixed duration which will depend on the event

and the number of athletes in that age group. The result of the scheduling process will be a start and finish time for each event

and an indication of which location resource was allocated to that event. The age group is considered a “resource” but we don’t

need to worry about which instance to allocate as there is only one instance of each age group at the competition.

Provided Skeleton Solution

For this assignment you have been provided with a skeleton solution (in the form of a Visual Studio 2019 Solution) that you must

use. The Solution consists of 9 Visual Studio Projects as illustrated below.

The three projects with a red border are the ones you need to complete:

1. FSharpGeneticAlgorithm (an F# library for implementing a Genetic Algorithm)

2. ScheduleModel (which includes the fitness function to be used for Athletics Scheduling)

3. CSharpGeneticAlgorithm (an alternative C# library for implementing a Genetic Algorithm).

The skeleton code included in each of those projects provide more detailed implementation instructions.

The remaining six projects have already been implemented and may not be altered in any way. They include:

• An F# library called RandomMonad that your F# implementation of the Genetic Algorithm will use when it needs to make

random choices (see explanation on next page)

• An F# library called TSPModel that includes the fitness function to be used for the TSP problem.

• Two separate sets of unit tests for the FsharpGeneticAlgorithm library and the ScheduleModel library. If you have

implemented those libraries correctly, all unit tests should pass.

• Two separate GUI applications (TSPView and ScheduleView) which provide a dynamic visualization of the TSP and

Athletics Scheduling problems as they are being optimized. Both GUI applications are built using .NET Window

Presentation Foundation (WPF) and use the MVVM pattern.

MVVM (Model-View-ViewModel)

The GUI apps uses the Model-View-ViewModel (MVVM) architectural pattern. See:

• https://en.wikipedia.org/wiki/Model-view-viewmodel,

• https://docs.microsoft.com/en-us/windows/uwp/data-binding/data-binding-and-mvvm,

• https://docs.microsoft.com/en-us/xamarin/xamarin-forms/enterprise-application-patterns/mvvm,

• https://blogs.msdn.microsoft.com/msgulfcommunity/2013/03/13/understanding-the-basics-of-mvvm-design-pattern/)

The GUI apps are split into 3 components: The Model, The View and the ViewModel. The model provides data structures for

representing objects in the domain as well as basic “business logic” for the application domain. The View is the part of the

application that determines what the user sees on the screen and what user interactions (clicks, keyboard, gestures, etc) are

allowed. The ViewModel acts as a bridge between the View and the Model:

https://documentation.devexpress.com/WPF/15112/MVVM-Framework

• The View is included in the GUI app in the form of a WPF window named MainWindow.xaml. The ViewModel is also contained

in the GUI app via a class named AppViewModel.cs. The Model is implemented in the TSPModel and ScheduleModel libraries

respectively, together with the Genetic Algorithm libraries. Both GUI apps are set up so the user can dynamically switch from

using your F# version of the Genetic Algorithm to your C# version of the Genetic Algorithm. Input files for ScheduleView can

be found in the TestCompetitions folder.

Figure 1: TSPView GUI app

Figure 2: ScheduleView GUI app

The Rand Monad

One of the F# modules provided to you is RandMonad. We will talk about Monads later in the semester, but for now it is sufficient

to understand that this Monad is designed to allow our Genetic Algorithm to make random decisions. However, one of the key

advantages of functional programming is the use of pure functions. A pure function will produce the same result every time if

called again with the same parameters. Any function that makes random decisions is therefore not going to be a pure function.

To produce random values, we need a random number generator. A random number generator can generate a sequence of

pseudo random numbers. In .NET we can create a random number generator by calling new System.Random(seed), where

seed is an integer. If we call new System.Random multiple times, but with the same seed, then we will get the same sequence of

pseudo random numbers every time. So, given a particular seed, the system becomes deterministic. The other problem with

random number generators is that they are stateful.

Consider:

var random = new System.Random(42);

var v1 = random.Next();

var v2 = random.Next();

Each time we call the Next method the internal state of the random object is changed, so the second call to random.Next() is likely

to return a different value than the first call to random.Next (even though we are using the same random number generator and

have not altered the parameters). We can think of the random number generator as generating an infinite sequence of numbers.

The first call to random.Next takes the first value in that sequence and the next call takes the second value in this sequence.

In order to make our genetic algorithm implementation more deterministic and purer, we are going to abstract the use of the

random number generator by wrapping it inside a monad which enable us to avoid directly creating or using random number

generators. In F# to use a Monad we make use of a Computational Expression. Our RandomMonad provides a

ComputationalBuilder called rand to create Computational Expressions. The following example from TSPModel illustrates how

we make use of the random monad:

let randomCity width height: Rand =

rand {

let! randomX = intRange 0 width

let! randomY = intRange 0 height

return { x = randomX; y = randomY }

}

First, notice that the code in the function is wrapped in rand { … }. This produces a Rand value, in this case a Rand. The

intRange function from the RandomMonad module returns a value of type Rand, i.e., a random integer. A random integer is

different to a regular integer. We cannot for example add or subtract random integers. Notice the exclamation mark after the let.

If we had instead said (without the exclamation mark):

let random1 = intRange 0 width

then random1 would be of type Rand. However, by using let!, random1 gets an integer value. The let! allows us to

“unwrap” the random monad and allows us to get our hands on the actual random value hidden inside. But we can only use let!

within a rand computational expression. So, the final result ends up being a random value, in this case a randomly generated

City. So, the monad provides us a way to unwrap, various random values, but the final result gets wrapped up again. Ultimately,

we need to provide a random number generator for such functions to be able to be evaluated, but that is done just once at the

root our application – and if we use the same seed each time we run our application then the entire program will run

deterministically every time. Importantly, this allows us to create deterministic unit tests for individual functions and for the entire

program.

The other important thing to note about the Rand monad is that the order in which we list the let! statements is significant,

because each time we unwrap a random value we are implicitly consuming values from a stateful random number generator. For

example, the following function definition would produce different results to the one above (even if the same random number

generator is used):

let randomCity width height: Rand =

rand {

let! randomY = intRange 0 height

let! randomX = intRange 0 width

return { x = randomX; y = randomY }

}

Details of the Genetic Algorithm Implementation

We start with a randomly generated population of individuals. In our case, each individual will be a randomly generated

permutation of integers. All individuals in a population always have the same number of genes.

In each generation we create offspring by selecting parents via a process of natural selection. There are many different selection

algorithms (https://en.wikipedia.org/wiki/Selection) , but in our case we will use a process called tournament selection. From the

entire population we select a field of N individuals who will compete. The individual with the highest fitness value in the field is

then selected as the winner and gets to mate. In our implementation, the parameter N will be 2. i.e., two individuals will be

selected to compete in each tournament. Each of the N individuals is selected independently, so there is a small chance that the

same individual may be selected twice and hence compete with itself (which is not a problem). This tournament selection process

is carried out twice to select both parents – there is no notion of gender.

Once we have two parents, we combine their genetic material via a cross over process to create the offspring. There are many

different crossover algorithms (https://en.wikipedia.org/wiki/Crossover), but in our case the cross over will happen via a process

called Ordered Crossover (OX). We randomly split the first parent’s genes into two sequences such that the first part and the last

part each have at least one gene. The first part of the first parent’s genes becomes the first part of the offspring’s genes. The last

part of the offspring’s genes is determined by adding genes from the last part of the first parent but reordered according to the

order in which they appear in the second parent. For example, if parent1 = [0,3,5,4,2,1,6] and parent2 = [6,4,2,1,0,3,5] and the

split point is 4 then the first 4 genes come from parent1 [0,3,5,4] and the remaining genes [2,1,6] are ordered according to parent2

i.e. [6,2,1] because 6 comes before 2 and 2 comes before 1 in parent2. So, the child in this example will be [0,3,5,4,6,2,1].

Once we have combined the genetic material from the two parents, sometimes (with probability = 0.15) a mutation occurs which

randomly changes the makeup of the offspring’s genes. There are many different mutation algorithms

(https://en.wikipedia.org/wiki/Mutation), but in our case we will perform a reverse mutation. We randomly split the genes into

three sequences, start, middle and end (such that the middle section has at least two genes. The start and end sequences remain

unchanged, but the genes in the middle are reversed in order. For example, if we randomly split at positions 2 and 4, then

[0,3,5,4,2,1,6] would mutate into [0,3,2,4,5,1,6].

Once a specified number of offspring have been produced, the next generation is then formed by combining the offspring with

some of the individuals from the previous generation. Many different algorithms exist, but in our case, we will use a process called

Elitism Selection. We combine all the offspring together with the N fittest individuals from the previous generation (where N = 10).

This ensures that we do not lose the best solution found so far.

There are also various methods for deciding how many generations to evolve before terminating the application. Given the

heuristic nature of the optimization process, we may never know for sure when we have found the best possible solution. We

might search forever and never find a better solution or a better solution might be just a generation away. We therefore leave it

to the end-user to decide when to terminate the search. Our algorithm will keep searching forever, producing an infinite sequence

of the best individuals from each successive generation.

To obtain good results with genetic algorithms, it is important to experiment with various parameters. In our case we will

generally use an initial population of 100 individuals. Using more individuals creates more genetic diversity but takes longer to

simulate each generation.

The Array Type

Unlike lists and sequences, arrays in F# are mutable, meaning you can update the values of individual elements after the array has

been created. For example, the following changes the 3rd element of the array to 32.

myArray.[2] <- 32

Such impure F# code is forbidden in this assignment. The goal of this assignment is to learn the art of pure functional programming.

We do however use the array type extensively in the Genetic Algorithm module. We do not use arrays because they can be updated

after they have been created; we use them only because they are more efficient that lists to lookup a particular element. Element

lookup with arrays in O(1) whereas it is O(N) for lists and sequences. i.e., with a list or sequence, if you wanted to access the 100th

element the system would need to traverse element by element from the start until it got to the 100th element, whereas with an

array it can jump straight to the 100th element in constant time.

The following are some useful Array functions that I have used in my sample solution:

• Array.append

• Array.except

• Array.filter

• Array.init

• Array.init

• Array.isEmpty

• Array.map

• Array.map2

• Array.maxBy

• Array.rev

• Array.sortBy

• Array.sum

• Array.take

• Array.truncate

• Array.unfold

What to Submit

1. A 1-to-2-page PDF report discussing your experience and comparing the two approaches (F# pure functional and C#

object-oriented imperative). Your comparison should include a discussion on the efficiency and effectiveness of the two

approaches. You should discuss which was easier to program, which code is easier to read, understand and maintain,

which is more concise, and which produces more efficient code. Provide measures were applicable to support your

claims.

2. A zip file containing your entire Visual Studio Solution folder.

You should work with the skeleton Visual Studio solution provided and make changes only to the following projects:

• FSharpGeneticAlgorithm

• CSharpGeneticAlgorithm

• ScheduleModel

Note:

• All occurrences of // TODO: add correct implementation here comment should be replaced by an actual

implementation.

• Extra helper functions and methods should be added as needed. Complex functions and methods should be

broken down into simpler functions. Ensure you use meaningful names for all functions, methods, parameters,

and variables.

• Ideally, all 8770 unit-tests should pass.

To reduce file size when submitting you should remove the following:

• .vs folder

• bin folders

• obj folders

• Visual Studio solution files except for CAB402GeneticAlgorithm.sln

Everything remaining should be added to a compressed zip file with a name of the form n1234567.zip

Note: this must be a zip file, not a tar file, not a rar file, not an iso file, etc.

When we mark your assignment, we will:

1. Unzip your zip file

2. Double click on CAB402GeneticAlgorithm.sln to open your solution in Visual Studio 2019

3. Perform a Rebuild Solution (this should cause any required packages to download as necessary).

4. Run all the unit tests via the Test Explorer Window

5. Start your TSPView and ScheduleView applications and test that they behave as expected, trying both the F#

and C# versions of the Genetic Algorithm library.

6. We will then browse your source code and assess it against the assessment criteria.

Assignment 1

Due: 23rd April 2021

Worth: 30%

The purpose of this assignment is to develop your functional programming skills by implementing a non-trivial application using

F#. The principal focus will be on learning to program in a “pure” functional style – i.e., without making use of any mutable state.

In order to contrast this pure functional style of programming with the more traditional imperative (impure) and object-oriented

paradigms, you will develop two separate implementations of the Genetic Algorithm library:

1. A pure functional implementation using F#

2. An object-oriented C# implementation

Required Software

1. Latest version of Visual Studio 2019 (with .NET desktop development and .NET 5.0)

Genetic Algorithms

For many so-called Combinatorial Problems, there exist an exponential number of possible solutions. For sufficiently large

problems it therefore becomes prohibitively time consuming to perform a brute force analysis of every possible solution. We must

resort to some form of heuristic algorithm that aims to find a good solution, but not necessarily the best possible solution. One

such class of heuristic algorithms is Genetic algorithms which are based on the process of evolution and natural selection as occurs

in the wild. We start with some population of individuals, those individuals mate to produce offspring. This mating process creates

children that have some combination of genes derived from their parents. During this reproductive process, some genes might

also mutate (i.e., accidently change at random). Such random mutations are generally harmful to the child, but occasionally they

might result in a fitter mutant offspring. Natural selection means that fitter individuals are more likely to mate and pass on their

genetic material to the next generation, so over time, the population as a whole tends to get fitter.

In a genetic algorithm, each individual in the population represents a particular proposed solution to a specific combinatorial

problem. So, to use a genetic algorithm to solve a combinatorial problem we must first decide how we will encode a proposed

problem solution as a sequence of genes. Each gene will represent some particular aspect of the solution. We can use whatever

data type we like to represent each gene. For example, we could use binary bits, integers, real numbers, characters, etc. The choice

will depend on the particular problem we are trying to solve.

If natural selection involves “survival of the fittest”, we need to provide a means for determining which individuals are fitter or

better than others. We need to provide a fitness function that takes a sequence of genes as input and returns a numeric fitness

value (where higher means better). The fitness function depends on what aspect of the problem we are trying to optimize. If we

want to optimize for some different property, then we just need to change the fitness function used and the evolutionary process

will then tend to find better and better solutions according to that fitness criteria.

In this assignment we are going to use Genetic Algorithms to solve two different combinatorial problems:

1. Travelling Salesperson Problem (https://en.wikipedia.org/wiki/Travelling_salesman_problem)

The first is the Travelling Salesperson Problem (TSP), a well-known NP-hard combinatorial problem. Given a set of cities at specific

locations, the challenge is for the salesperson to visit each city precisely once and then return to where they started, while

travelling the least total distance. Visiting the cities in different orders will result in different total distances, so when encoding a

particular solution to the TSP problem as a sequence of genes, it is natural to use a sequence of integers representing the order

in which the cities will be visited. For example, the sequence [2,4,3,1,5] means that we would start at city 2, then travel to city 4,

then to city 3 and so on before eventually returning to city 2. Given a particular order in which cities will be visited we can compute

the total distance travelled, so the fitness function is based on total distance travelled, however, since we want to minimize the

total distance travelled, we actually use the negative of the total distance travelled as our fitness value, since we want a higher

fitness to correspond to a better solution.

2. The Resource Constrained Scheduling Problem (RCSP) (https://en.wikipedia.org/wiki/Genetic_algorithm_scheduling)

The resource constrained scheduling problem (RCSP) is another well known and important combinatorial problem. We are given

a set of jobs (or projects) that need to be completed. There are also a finite number of various types of resources that are needed

to help complete the jobs. Each job requires a particular number of these various resources. For example, job 1 may require 2

resources of type A and 1 resource of type B, while job 2 might require just 1 resource of type A. Each job also has a specific

duration. The resources used by a job need to be available for the entire duration of that job, i.e., they can not be used by any

other job during that time period. The resources are renewable, meaning that once we are finished using them for one job, we

can use them again for some other job. We are also given an objective function that we are trying to optimize. Often, we are just

trying to minimize the total duration required to complete all jobs. A solution to the RCSP involves determining a start time for

each of the jobs and an allocation of resources.

One popular method for creating such a solution is the Serial Schedule Generation Scheme. This algorithm involves scheduling

each of the jobs, one by one in a particular order. For each job we seek to determine the earliest possible time that the job could

be feasibly scheduled given the jobs that have already been scheduled. When we say feasibly scheduled, we mean that for the

entire duration of that job (from start time to start time plus the job duration), that we can allocate the required resources for

that job such that those allocated resources are not being used by any of the other jobs during that time period. If we change the

order in which we schedule the jobs, then the resulting schedule will change and possibly have a better or worse total duration

required to complete all jobs.

So, in searching for the best possible schedule, rather than considering every possible schedule, we instead just need to determine

the order in which we should schedule the jobs, because a given scheduling order leads deterministically to a specific schedule.

Solving a RCSP problem using a genetic algorithm is therefore very similar to solving a TSP problem. In both cases we are seeking

an ordering (or permutation). In one case the order in which cities should be visited, and in the other the order in which we should

serially schedule the jobs. So, we use the same genetic representation as for TSP, a sequence of integers (which must always be a

permutation). The only difference is the fitness function. In the case of the RCSP problem, we take the job order provided by a

particular individual’s genes and use it to conduct a serial schedule generation. From that we can determine the finish time of the

latest job and return the negative of that time value (since a shorter total duration is considered better).

During serial schedule generation, determining the earliest possible start time for each event can be computationally expensive

as it may involve considering many possible start times before we eventually find one that works. In order to make this algorithm

more efficient, we exploit the following observation: The earliest possible start time for a job is always going to be either time 0

(if it can be started immediately), or it will be the precise finish time of some other job that has already been scheduled. So, rather

than testing every possible potential start time, we only need to consider either 0 or the distinct finish times of jobs that have

already been scheduled. But we can leverage this idea even further. In determining whether some job can start at say time t0

(where t0 is either 0 or one of the previous finish time), we then need to ensure that the resources that we are proposing to

allocate to this job are available for the entire duration of that job (i.e., times t such t0 <= t < t0 + duration). However, based on

the above idea, we do not actually need to check at every time point between t0 and t0+duration. We need only check at the time

points within that period which also happen to be a finish time of one of the previous jobs – because it is only at those time points

that resource usage changes. So, we can save the time checking at all the other time points within that period.

If job 1 requires one resource of type A and there are a total of 3 resources of type A, then in developing a schedule we need to

decide not only the start time of job 1, but also which resource of type A we will allocate to it. Otherwise, it would be difficult to

ensure that particular resource instance will be able to be used solely by job 1 for its entire duration. We therefore number each

resource instance from 0 up to N-1 where N is the finite number of resources of that type available.

Athletics Event Scheduling

The resource constrained scheduling problem is applicable to many real-world problems, from scheduling exams or staff rosters

or factory manufacturing schedules. In this assignment we are going to consider a real-world problem of scheduling the events for

a junior athletics competition. We are given a list of events that each age group of athletes will compete in during the competition.

For example:

U15-17G Javelin

U8B 70m Sprint

U13-14B Long Jump

U15-17G 700m Walk

etc …

Each event requires two resources. It requires the group of athletes in that age group and it requires a suitable location to conduct

the event. Each different type of event requires a different type of location. For example, the 70m Sprint and the 700m Walk both

require a running track, while the Long Jump event require a sand pit. For a given competition arena, there are a fixed set of

locations which are available for each type of event. For example, there may be 4 sand pits, but only 1 running track. When

scheduling an athletics event (using serial schedule generation) we must ensure that both required “resources” are available for

the entire duration of that event: the group of athletes in that age group need to be available and the location that will be allocated

to that event, e.g., sand pit number 2, needs to be available. Each event will have a fixed duration which will depend on the event

and the number of athletes in that age group. The result of the scheduling process will be a start and finish time for each event

and an indication of which location resource was allocated to that event. The age group is considered a “resource” but we don’t

need to worry about which instance to allocate as there is only one instance of each age group at the competition.

Provided Skeleton Solution

For this assignment you have been provided with a skeleton solution (in the form of a Visual Studio 2019 Solution) that you must

use. The Solution consists of 9 Visual Studio Projects as illustrated below.

The three projects with a red border are the ones you need to complete:

1. FSharpGeneticAlgorithm (an F# library for implementing a Genetic Algorithm)

2. ScheduleModel (which includes the fitness function to be used for Athletics Scheduling)

3. CSharpGeneticAlgorithm (an alternative C# library for implementing a Genetic Algorithm).

The skeleton code included in each of those projects provide more detailed implementation instructions.

The remaining six projects have already been implemented and may not be altered in any way. They include:

• An F# library called RandomMonad that your F# implementation of the Genetic Algorithm will use when it needs to make

random choices (see explanation on next page)

• An F# library called TSPModel that includes the fitness function to be used for the TSP problem.

• Two separate sets of unit tests for the FsharpGeneticAlgorithm library and the ScheduleModel library. If you have

implemented those libraries correctly, all unit tests should pass.

• Two separate GUI applications (TSPView and ScheduleView) which provide a dynamic visualization of the TSP and

Athletics Scheduling problems as they are being optimized. Both GUI applications are built using .NET Window

Presentation Foundation (WPF) and use the MVVM pattern.

MVVM (Model-View-ViewModel)

The GUI apps uses the Model-View-ViewModel (MVVM) architectural pattern. See:

• https://en.wikipedia.org/wiki/Model-view-viewmodel,

• https://docs.microsoft.com/en-us/windows/uwp/data-binding/data-binding-and-mvvm,

• https://docs.microsoft.com/en-us/xamarin/xamarin-forms/enterprise-application-patterns/mvvm,

• https://blogs.msdn.microsoft.com/msgulfcommunity/2013/03/13/understanding-the-basics-of-mvvm-design-pattern/)

The GUI apps are split into 3 components: The Model, The View and the ViewModel. The model provides data structures for

representing objects in the domain as well as basic “business logic” for the application domain. The View is the part of the

application that determines what the user sees on the screen and what user interactions (clicks, keyboard, gestures, etc) are

allowed. The ViewModel acts as a bridge between the View and the Model:

https://documentation.devexpress.com/WPF/15112/MVVM-Framework

• The View is included in the GUI app in the form of a WPF window named MainWindow.xaml. The ViewModel is also contained

in the GUI app via a class named AppViewModel.cs. The Model is implemented in the TSPModel and ScheduleModel libraries

respectively, together with the Genetic Algorithm libraries. Both GUI apps are set up so the user can dynamically switch from

using your F# version of the Genetic Algorithm to your C# version of the Genetic Algorithm. Input files for ScheduleView can

be found in the TestCompetitions folder.

Figure 1: TSPView GUI app

Figure 2: ScheduleView GUI app

The Rand Monad

One of the F# modules provided to you is RandMonad. We will talk about Monads later in the semester, but for now it is sufficient

to understand that this Monad is designed to allow our Genetic Algorithm to make random decisions. However, one of the key

advantages of functional programming is the use of pure functions. A pure function will produce the same result every time if

called again with the same parameters. Any function that makes random decisions is therefore not going to be a pure function.

To produce random values, we need a random number generator. A random number generator can generate a sequence of

pseudo random numbers. In .NET we can create a random number generator by calling new System.Random(seed), where

seed is an integer. If we call new System.Random multiple times, but with the same seed, then we will get the same sequence of

pseudo random numbers every time. So, given a particular seed, the system becomes deterministic. The other problem with

random number generators is that they are stateful.

Consider:

var random = new System.Random(42);

var v1 = random.Next();

var v2 = random.Next();

Each time we call the Next method the internal state of the random object is changed, so the second call to random.Next() is likely

to return a different value than the first call to random.Next (even though we are using the same random number generator and

have not altered the parameters). We can think of the random number generator as generating an infinite sequence of numbers.

The first call to random.Next takes the first value in that sequence and the next call takes the second value in this sequence.

In order to make our genetic algorithm implementation more deterministic and purer, we are going to abstract the use of the

random number generator by wrapping it inside a monad which enable us to avoid directly creating or using random number

generators. In F# to use a Monad we make use of a Computational Expression. Our RandomMonad provides a

ComputationalBuilder called rand to create Computational Expressions. The following example from TSPModel illustrates how

we make use of the random monad:

let randomCity width height: Rand

rand {

let! randomX = intRange 0 width

let! randomY = intRange 0 height

return { x = randomX; y = randomY }

}

First, notice that the code in the function is wrapped in rand { … }. This produces a Rand value, in this case a Rand

intRange function from the RandomMonad module returns a value of type Rand

different to a regular integer. We cannot for example add or subtract random integers. Notice the exclamation mark after the let.

If we had instead said (without the exclamation mark):

let random1 = intRange 0 width

then random1 would be of type Rand

“unwrap” the random monad and allows us to get our hands on the actual random value hidden inside. But we can only use let!

within a rand computational expression. So, the final result ends up being a random value, in this case a randomly generated

City. So, the monad provides us a way to unwrap, various random values, but the final result gets wrapped up again. Ultimately,

we need to provide a random number generator for such functions to be able to be evaluated, but that is done just once at the

root our application – and if we use the same seed each time we run our application then the entire program will run

deterministically every time. Importantly, this allows us to create deterministic unit tests for individual functions and for the entire

program.

The other important thing to note about the Rand monad is that the order in which we list the let! statements is significant,

because each time we unwrap a random value we are implicitly consuming values from a stateful random number generator. For

example, the following function definition would produce different results to the one above (even if the same random number

generator is used):

let randomCity width height: Rand

rand {

let! randomY = intRange 0 height

let! randomX = intRange 0 width

return { x = randomX; y = randomY }

}

Details of the Genetic Algorithm Implementation

We start with a randomly generated population of individuals. In our case, each individual will be a randomly generated

permutation of integers. All individuals in a population always have the same number of genes.

In each generation we create offspring by selecting parents via a process of natural selection. There are many different selection

algorithms (https://en.wikipedia.org/wiki/Selection) , but in our case we will use a process called tournament selection. From the

entire population we select a field of N individuals who will compete. The individual with the highest fitness value in the field is

then selected as the winner and gets to mate. In our implementation, the parameter N will be 2. i.e., two individuals will be

selected to compete in each tournament. Each of the N individuals is selected independently, so there is a small chance that the

same individual may be selected twice and hence compete with itself (which is not a problem). This tournament selection process

is carried out twice to select both parents – there is no notion of gender.

Once we have two parents, we combine their genetic material via a cross over process to create the offspring. There are many

different crossover algorithms (https://en.wikipedia.org/wiki/Crossover), but in our case the cross over will happen via a process

called Ordered Crossover (OX). We randomly split the first parent’s genes into two sequences such that the first part and the last

part each have at least one gene. The first part of the first parent’s genes becomes the first part of the offspring’s genes. The last

part of the offspring’s genes is determined by adding genes from the last part of the first parent but reordered according to the

order in which they appear in the second parent. For example, if parent1 = [0,3,5,4,2,1,6] and parent2 = [6,4,2,1,0,3,5] and the

split point is 4 then the first 4 genes come from parent1 [0,3,5,4] and the remaining genes [2,1,6] are ordered according to parent2

i.e. [6,2,1] because 6 comes before 2 and 2 comes before 1 in parent2. So, the child in this example will be [0,3,5,4,6,2,1].

Once we have combined the genetic material from the two parents, sometimes (with probability = 0.15) a mutation occurs which

randomly changes the makeup of the offspring’s genes. There are many different mutation algorithms

(https://en.wikipedia.org/wiki/Mutation), but in our case we will perform a reverse mutation. We randomly split the genes into

three sequences, start, middle and end (such that the middle section has at least two genes. The start and end sequences remain

unchanged, but the genes in the middle are reversed in order. For example, if we randomly split at positions 2 and 4, then

[0,3,5,4,2,1,6] would mutate into [0,3,2,4,5,1,6].

Once a specified number of offspring have been produced, the next generation is then formed by combining the offspring with

some of the individuals from the previous generation. Many different algorithms exist, but in our case, we will use a process called

Elitism Selection. We combine all the offspring together with the N fittest individuals from the previous generation (where N = 10).

This ensures that we do not lose the best solution found so far.

There are also various methods for deciding how many generations to evolve before terminating the application. Given the

heuristic nature of the optimization process, we may never know for sure when we have found the best possible solution. We

might search forever and never find a better solution or a better solution might be just a generation away. We therefore leave it

to the end-user to decide when to terminate the search. Our algorithm will keep searching forever, producing an infinite sequence

of the best individuals from each successive generation.

To obtain good results with genetic algorithms, it is important to experiment with various parameters. In our case we will

generally use an initial population of 100 individuals. Using more individuals creates more genetic diversity but takes longer to

simulate each generation.

The Array Type

Unlike lists and sequences, arrays in F# are mutable, meaning you can update the values of individual elements after the array has

been created. For example, the following changes the 3rd element of the array to 32.

myArray.[2] <- 32

Such impure F# code is forbidden in this assignment. The goal of this assignment is to learn the art of pure functional programming.

We do however use the array type extensively in the Genetic Algorithm module. We do not use arrays because they can be updated

after they have been created; we use them only because they are more efficient that lists to lookup a particular element. Element

lookup with arrays in O(1) whereas it is O(N) for lists and sequences. i.e., with a list or sequence, if you wanted to access the 100th

element the system would need to traverse element by element from the start until it got to the 100th element, whereas with an

array it can jump straight to the 100th element in constant time.

The following are some useful Array functions that I have used in my sample solution:

• Array.append

• Array.except

• Array.filter

• Array.init

• Array.init

• Array.isEmpty

• Array.map

• Array.map2

• Array.maxBy

• Array.rev

• Array.sortBy

• Array.sum

• Array.take

• Array.truncate

• Array.unfold

What to Submit

1. A 1-to-2-page PDF report discussing your experience and comparing the two approaches (F# pure functional and C#

object-oriented imperative). Your comparison should include a discussion on the efficiency and effectiveness of the two

approaches. You should discuss which was easier to program, which code is easier to read, understand and maintain,

which is more concise, and which produces more efficient code. Provide measures were applicable to support your

claims.

2. A zip file containing your entire Visual Studio Solution folder.

You should work with the skeleton Visual Studio solution provided and make changes only to the following projects:

• FSharpGeneticAlgorithm

• CSharpGeneticAlgorithm

• ScheduleModel

Note:

• All occurrences of // TODO: add correct implementation here comment should be replaced by an actual

implementation.

• Extra helper functions and methods should be added as needed. Complex functions and methods should be

broken down into simpler functions. Ensure you use meaningful names for all functions, methods, parameters,

and variables.

• Ideally, all 8770 unit-tests should pass.

To reduce file size when submitting you should remove the following:

• .vs folder

• bin folders

• obj folders

• Visual Studio solution files except for CAB402GeneticAlgorithm.sln

Everything remaining should be added to a compressed zip file with a name of the form n1234567.zip

Note: this must be a zip file, not a tar file, not a rar file, not an iso file, etc.

When we mark your assignment, we will:

1. Unzip your zip file

2. Double click on CAB402GeneticAlgorithm.sln to open your solution in Visual Studio 2019

3. Perform a Rebuild Solution (this should cause any required packages to download as necessary).

4. Run all the unit tests via the Test Explorer Window

5. Start your TSPView and ScheduleView applications and test that they behave as expected, trying both the F#

and C# versions of the Genetic Algorithm library.

6. We will then browse your source code and assess it against the assessment criteria.