i have a file
SLA 461 AI SP 2023 Program 2 – Genetic Algorithm For this program, you will use a genetic algorithm to attempt to build a space utilization schedule. A client agency has been attempting to develop a better method of scheduling their activities. There are many competing factors in scheduling, so a single ideal schedule may not be possible. (This is a simplified version of the real problem.) · All of these activities are scheduled for MWF, for 50 minutes, so we need only determine the time slot, room, and facilitator for each activity. · The Sophisticated Learning Association (SLA) has several activities available and has full control of those rooms and can put activities into any time slot they wish. (Typically this is not the case in real world scheduling for potentially conflicting departments or agencies.) · Each facilitator tends to work best overseeing a small group of activities, but the same activity isn’t always provided by the same facilitator, and the same facilitator doesn’t always teach the same activity. Thus, each activity has a list of a few facilitators who are preferred for overseeing that activity, and a few others who are able to “cross over” to that activity. Any activity can also be overseen by any facilitator, but this is a stopgap if no other facilitators are available. · You are given a list of all facilitators. Use this to randomly assign activity assignments and for random substitution (mutation). Use the preferred/other listing for scoring purposes, not for selecting faculty. (This keeps the generation/substitution process simple, and allows a broader exploration of the state space.) · Each activities has an expected enrollment. Any activities should be in a room big enough to hold the expected enrollment. Likewise, a room more than 3 times the expected enrollment can be used, but is too big, and there is a smaller penalty in that case. · There are 2 sections (A and B) of some activity. · Your program will assign, for each activity: · Room · Time · Facilitator · Initially, this assignment will be random. You’ll create a population of random possible schedules (N >= 500) and then apply a genetic algorithm to improve it. Fitness function: · For each activity, fitness starts at 0. · Activity is scheduled at the same time in the same room as another of the activities: -0.5 · Room size: · Activities is in a room too small for its expected enrollment: -0.5 · Activities is in a room with capacity > 3 times expected enrollment: -0.2 · Activities is in a room with capacity > 6 times expected enrollment: -0.4 · Otherwise + 0.3 · Activities is overseen by a preferred facilitator: + 0.5 · Activities is overseen by another facilitator listed for that activity: +0.2 · Activities is overseen by some other facilitator: -0.1 · Facilitator load: · Activity facilitator is scheduled for only 1 activity in this time slot: + 0.2 · Activity facilitator is scheduled for more than one activity at the same time: - 0.2 · Facilitator is scheduled to oversee more than 4 activities total: -0.5 · Facilitator is scheduled to oversee 1 or 2 activities*: -0.4 · Exception: Dr. Tyler is committee chair and has other demands on his time. *No penalty if he’s only required to oversee < 2 activities. · if any facilitator scheduled for consecutive time slots: same rules as for sla 191 and sla 101 in consecutive time slots—see below. activity-specific adjustments: · the 2 sections of sla 101 are more than 4 hours apart: + 0.5 · both sections of sla 101 are in the same time slot: -0.5 · the 2 sections of sla 191 are more than 4 hours apart: + 0.5 · both sections of sla 191 are in the same time slot: -0.5 · a section of sla 191 and a section of sla 101 are overseen in consecutive time slots (e.g., 10 am & 11 am): +0.5 · in this case only (consecutive time slots), one of the activities is in roman or beach, and the other isn’t: -0.4 · it’s fine if neither is in one of those buildings, of activity; we just want to avoid having consecutive activities being widely separated. · · a section of sla 191 and a section of sla 101 are taught separated by 1 hour (e.g., 10 am & 12:00 noon): + 0.25 · a section of sla 191 and a section of sla 101 are taught in the same time slot: -0.25 computing the fitness function: · the fitness function for a schedule is the sum of the fitness of the individual activities in it (i.e. add up the scores for each activities using the above rubric, and sum the activities). · use softmax* normalization to convert fitness scores into a probability distribution.1 *(the link is an example of a library implementation for python’s scipy but this is a common function in other libraries) · as you select pairs for reproduction, whether you produce 1 offspring per pairing or both possible offspring is an implementation decision. · programming note: access to the parent population is read-only; copy 2 parents, produce some offspring, add them to a next-generation pool. this can parallelize nicely. · start with a mutation rate of 0.01(λ); if an item is selected for mutation, use random selection. · note: this value might need to be adjusted (see note below(δ)). · run at least 100 generations (g). continue until the improvement in average fitness for generation g is less than 1% improvement over generation g100. report the best fitness from the final generation and print the schedule to an output file. (don’t worry unduly about output formatting but please do try to make it legible.) (δ)note on rate: once your program is running, note the fitness you get, and then cut the mutation (λ/2) rate in half. as long as your results continue to improve, continue cutting the mutation rate in half until things appear to be stable. 1alternatively, rather than computing a probability distribution, you can keep your schedules in a minheap. the item at the top is the least-fit individual and is selected for removal. select any 2 schedules at random from the heap as parents for a replacement. find the fitness of the new offspring, put it at the top of the heap, and restore the heap property. this ensures we are always removing the least-fit individual. a more-fit individual will stay farther down in the heap longer, and thus have more opportunities to reproduce, than a lower-fitness individual which will find itself migrating to the top of the heap as breeding continues and the population gradually improves. in this case, a generation is n replacements, where n is the size of the population. (if you have a heap of size 500, then 500 remove/replace cycles constitute 1 generation.) this doesn’t parallelize as nicely as the other method, but bypasses the need for normalization completely. other programming notes: · your chosen programing environment’s core or library supplied random number generator should be fine for this project; there’s not likely to be any significant improvement in performance when implementing any more complex generator. (the generators in early compilers did have some definite weaknesses, but almost all modern languages now use the mersenne twister or a cryptographic or hash-based rng, more than strong enough for our purposes.) turn in: · your source code: python, c++, c#, java · sample output (screen captures / generated text) · a short report (probably a page or so) in .doc/.docx/.pdf format, discussing: i) what were the challenges in writing the program? or did it seem to go smoothly from the beginning? ii) what do you think of the schedule your program produced? does it have anything that still looks odd or out of place? iii) how would you improve the program, or change the fitness function? iv) anything else you feel like discussing, asking about, bragging about, etc. appendix: 10 activities, 7 rooms, and 6 times facilitators: lock, glen, banks, richards, shaw, singer, uther, tyler, numen, zeldin sla100a, sla100b: expected enrollment: 50 preferred facilitators: glen, lock, banks, zeldin other facilitators: numen, richards sla191a, sla191b: expected enrollment: 50 preferred facilitators: glen, lock, banks, zeldin other facilitators: numen, richards sla201: expected enrollment: 50 preferred facilitators: glen, banks, zeldin, shaw other facilitators: numen, richards, singer sla291: expected enrollment: 50 preferred facilitators: lock, banks, zeldin, singer other facilitators: numen, richards, shaw, tyler sla303: expected enrollment: 60 preferred facilitators: glen, zeldin, banks other facilitators: numen, singer, shaw sla304: expected enrollment: 25 preferred facilitators: glen, banks, tyler other facilitators: numen, singer, shaw, richards, uther, zeldin sla394: expected enrollment: 20 preferred facilitators: tyler, singer other facilitators: richards, zeldin, sla449: expected enrollment: 60 preferred facilitators: tyler, singer, shaw other facilitators: zeldin, uther sla451: expected enrollment: 100 preferred facilitators: tyler, singer, shaw other facilitators: zeldin, uther, richards, banks room capacity slater 003 45 roman 216 30 loft 206 75 roman 201 50 loft 310 108 beach 201 60 beach 301 75 logos 325 450 frank 119 60 all rooms are available for the following time slots. times: 10 am 11 am 12 pm 1 pm 2 pm 3 pm 2="" activities.="" ·="" if="" any="" facilitator="" scheduled="" for="" consecutive="" time="" slots:="" same="" rules="" as="" for="" sla="" 191="" and="" sla="" 101="" in="" consecutive="" time="" slots—see="" below.="" activity-specific="" adjustments:="" ·="" the="" 2="" sections="" of="" sla="" 101="" are="" more="" than="" 4="" hours="" apart:="" +="" 0.5="" ·="" both="" sections="" of="" sla="" 101="" are="" in="" the="" same="" time="" slot:="" -0.5="" ·="" the="" 2="" sections="" of="" sla="" 191="" are="" more="" than="" 4="" hours="" apart:="" +="" 0.5="" ·="" both="" sections="" of="" sla="" 191="" are="" in="" the="" same="" time="" slot:="" -0.5="" ·="" a="" section="" of="" sla="" 191="" and="" a="" section="" of="" sla="" 101="" are="" overseen="" in="" consecutive="" time="" slots="" (e.g.,="" 10="" am="" &="" 11="" am):="" +0.5="" ·="" in="" this="" case="" only="" (consecutive="" time="" slots),="" one="" of="" the="" activities="" is="" in="" roman="" or="" beach,="" and="" the="" other="" isn’t:="" -0.4="" ·="" it’s="" fine="" if="" neither="" is="" in="" one="" of="" those="" buildings,="" of="" activity;="" we="" just="" want="" to="" avoid="" having="" consecutive="" activities="" being="" widely="" separated.="" ·="" ·="" a="" section="" of="" sla="" 191="" and="" a="" section="" of="" sla="" 101="" are="" taught="" separated="" by="" 1="" hour="" (e.g.,="" 10="" am="" &="" 12:00="" noon):="" +="" 0.25="" ·="" a="" section="" of="" sla="" 191="" and="" a="" section="" of="" sla="" 101="" are="" taught="" in="" the="" same="" time="" slot:="" -0.25="" computing="" the="" fitness="" function:="" ·="" the="" fitness="" function="" for="" a="" schedule="" is="" the="" sum="" of="" the="" fitness="" of="" the="" individual="" activities="" in="" it="" (i.e.="" add="" up="" the="" scores="" for="" each="" activities="" using="" the="" above="" rubric,="" and="" sum="" the="" activities).="" ·="" use="" softmax*="" normalization="" to="" convert="" fitness="" scores="" into="" a="" probability="" distribution.1="" *(the="" link="" is="" an="" example="" of="" a="" library="" implementation="" for="" python’s="" scipy="" but="" this="" is="" a="" common="" function="" in="" other="" libraries)="" ·="" as="" you="" select="" pairs="" for="" reproduction,="" whether="" you="" produce="" 1="" offspring="" per="" pairing="" or="" both="" possible="" offspring="" is="" an="" implementation="" decision.="" ·="" programming="" note:="" access="" to="" the="" parent="" population="" is="" read-only;="" copy="" 2="" parents,="" produce="" some="" offspring,="" add="" them="" to="" a="" next-generation="" pool.="" this="" can="" parallelize="" nicely.="" ·="" start="" with="" a="" mutation="" rate="" of="" 0.01(λ);="" if="" an="" item="" is="" selected="" for="" mutation,="" use="" random="" selection.="" ·="" note:="" this="" value="" might="" need="" to="" be="" adjusted="" (see="" note="" below(δ)).="" ·="" run="" at="" least="" 100="" generations="" (g).="" continue="" until="" the="" improvement="" in="" average="" fitness="" for="" generation="" g="" is="" less="" than="" 1%="" improvement="" over="" generation="" g100.="" report="" the="" best="" fitness="" from="" the="" final="" generation="" and="" print="" the="" schedule="" to="" an="" output="" file.="" (don’t="" worry="" unduly="" about="" output="" formatting="" but="" please="" do="" try="" to="" make="" it="" legible.)="" (δ)note="" on="" rate:="" once="" your="" program="" is="" running,="" note="" the="" fitness="" you="" get,="" and="" then="" cut="" the="" mutation="" (λ/2)="" rate="" in="" half.="" as="" long="" as="" your="" results="" continue="" to="" improve,="" continue="" cutting="" the="" mutation="" rate="" in="" half="" until="" things="" appear="" to="" be="" stable.="" 1="" alternatively,="" rather="" than="" computing="" a="" probability="" distribution,="" you="" can="" keep="" your="" schedules="" in="" a="" minheap.="" the="" item="" at="" the="" top="" is="" the="" least-fit="" individual="" and="" is="" selected="" for="" removal.="" select="" any="" 2="" schedules="" at="" random="" from="" the="" heap="" as="" parents="" for="" a="" replacement.="" find="" the="" fitness="" of="" the="" new="" offspring,="" put="" it="" at="" the="" top="" of="" the="" heap,="" and="" restore="" the="" heap="" property.="" this="" ensures="" we="" are="" always="" removing="" the="" least-fit="" individual.="" a="" more-fit="" individual="" will="" stay="" farther="" down="" in="" the="" heap="" longer,="" and="" thus="" have="" more="" opportunities="" to="" reproduce,="" than="" a="" lower-fitness="" individual="" which="" will="" find="" itself="" migrating="" to="" the="" top="" of="" the="" heap="" as="" breeding="" continues="" and="" the="" population="" gradually="" improves.="" in="" this="" case,="" a="" generation="" is="" n="" replacements,="" where="" n="" is="" the="" size="" of="" the="" population.="" (if="" you="" have="" a="" heap="" of="" size="" 500,="" then="" 500="" remove/replace="" cycles="" constitute="" 1="" generation.)="" this="" doesn’t="" parallelize="" as="" nicely="" as="" the="" other="" method,="" but="" bypasses="" the="" need="" for="" normalization="" completely.="" other="" programming="" notes:="" ·="" your="" chosen="" programing="" environment’s="" core="" or="" library="" supplied="" random="" number="" generator="" should="" be="" fine="" for="" this="" project;="" there’s="" not="" likely="" to="" be="" any="" significant="" improvement="" in="" performance="" when="" implementing="" any="" more="" complex="" generator.="" (the="" generators="" in="" early="" compilers="" did="" have="" some="" definite="" weaknesses,="" but="" almost="" all="" modern="" languages="" now="" use="" the="" mersenne="" twister="" or="" a="" cryptographic="" or="" hash-based="" rng,="" more="" than="" strong="" enough="" for="" our="" purposes.)="" turn="" in:="" ·="" your="" source="" code:="" python,="" c++,="" c#,="" java="" ·="" sample="" output="" (screen="" captures="" generated="" text)="" ·="" a="" short="" report="" (probably="" a="" page="" or="" so)="" in="" .doc/.docx/.pdf="" format,="" discussing:="" i)="" what="" were="" the="" challenges="" in="" writing="" the="" program?="" or="" did="" it="" seem="" to="" go="" smoothly="" from="" the="" beginning?="" ii)="" what="" do="" you="" think="" of="" the="" schedule="" your="" program="" produced?="" does="" it="" have="" anything="" that="" still="" looks="" odd="" or="" out="" of="" place?="" iii)="" how="" would="" you="" improve="" the="" program,="" or="" change="" the="" fitness="" function?="" iv)="" anything="" else="" you="" feel="" like="" discussing,="" asking="" about,="" bragging="" about,="" etc.="" appendix:="" 10="" activities,="" 7="" rooms,="" and="" 6="" times="" facilitators:="" lock,="" glen,="" banks,="" richards,="" shaw,="" singer,="" uther,="" tyler,="" numen,="" zeldin="" sla100a,="" sla100b:="" expected="" enrollment:="" 50="" preferred="" facilitators:="" glen,="" lock,="" banks,="" zeldin="" other="" facilitators:="" numen,="" richards="" sla191a,="" sla191b:="" expected="" enrollment:="" 50="" preferred="" facilitators:="" glen,="" lock,="" banks,="" zeldin="" other="" facilitators:="" numen,="" richards="" sla201:="" expected="" enrollment:="" 50="" preferred="" facilitators:="" glen,="" banks,="" zeldin,="" shaw="" other="" facilitators:="" numen,="" richards,="" singer="" sla291:="" expected="" enrollment:="" 50="" preferred="" facilitators:="" lock,="" banks,="" zeldin,="" singer="" other="" facilitators:="" numen,="" richards,="" shaw,="" tyler="" sla303:="" expected="" enrollment:="" 60="" preferred="" facilitators:="" glen,="" zeldin,="" banks="" other="" facilitators:="" numen,="" singer,="" shaw="" sla304:="" expected="" enrollment:="" 25="" preferred="" facilitators:="" glen,="" banks,="" tyler="" other="" facilitators:="" numen,="" singer,="" shaw,="" richards,="" uther,="" zeldin="" sla394:="" expected="" enrollment:="" 20="" preferred="" facilitators:="" tyler,="" singer="" other="" facilitators:="" richards,="" zeldin,="" sla449:="" expected="" enrollment:="" 60="" preferred="" facilitators:="" tyler,="" singer,="" shaw="" other="" facilitators:="" zeldin,="" uther="" sla451:="" expected="" enrollment:="" 100="" preferred="" facilitators:="" tyler,="" singer,="" shaw="" other="" facilitators:="" zeldin,="" uther,="" richards,="" banks="" room="" capacity="" slater="" 003="" 45="" roman="" 216="" 30="" loft="" 206="" 75="" roman="" 201="" 50="" loft="" 310="" 108="" beach="" 201="" 60="" beach="" 301="" 75="" logos="" 325="" 450="" frank="" 119="" 60="" all="" rooms="" are="" available="" for="" the="" following="" time="" slots.="" times:="" 10="" am="" 11="" am="" 12="" pm="" 1="" pm="" 2="" pm="" 3="">