这个作业是用Python人工智能完成受调度启发的调度问题开发最佳解决方案

COMP9414: Artificial Intelligence
Assignment 1: Fuzzy Scheduling
这项工作涉及为受调度启发的调度问题开发最佳解决方案。
制造工厂必须在不同的期限内完成多个客户订单的情况,
但是可能对任务以及任务之间的关系存在约束。任何数字
可以同时安排多个任务,但某些任务可能无法完成
在截止日期之前。延迟完成任务是可以接受的,但是会产生成本,为此
分配是每小时的简单(美元)任务延迟时间。
通过忽略订单并给出数字来指定这种情况下的模糊调度问题
任务,每个任务的持续时间以小时为单位。每个任务必须在同一天开始和完成,
在工作时间(上午9点至下午5点)内。此外,在单个任务上都可能存在约束
和两个任务之间。一种约束类型是任务可以有最后期限,可以是
“硬性”(必须在任何有效的时间表中满足最后期限)或“软性”(任务可能会延迟完成)
–尽管仍在下午5点或之前–但由于错过了截止日期,因此每小时收取“费用”。目的
是制定所有任务的总体时间表(在一周内),以最大程度地降低总成本
满足所有对任务的硬约束,所有延迟完成的任务中的所有任务。
从技术上讲,此分配是约束优化问题,问题
它具有诸如标准约束满足问题(CSP)之类的约束,而且还具有与每个解决方案相关的成本。对于此分配,您将实施一个贪婪算法来查找
指定并从文件中读取的模糊调度问题的最佳解决方案。然而,
与贪婪的搜索算法中介绍的贪婪搜索算法不同,这种贪婪算法具有
保证为任何问题找到最佳解决方案的属性(如果存在解决方案)。
您必须使用AIPython代码来满足约束条件,并进行搜索以开发贪婪的搜索
与启发式搜索一样,使用成本来指导搜索的方法。搜索将使用优先级
由启发式函数的值排序的队列,该函数为搜索中的每个节点提供成本。
在此分配中使用的启发式函数定义如下。搜索中的节点
是CSP,即每个状态都是具有变量,域和相同约束(以及成本)的CSP
估计)。状态空间中的过渡会根据弧的一致性实现域拆分。
目标状态是将值分配给所有满足所有约束的变量。
用于此分配的CSP是一组代表任务,成对的二进制约束的变量
任务的数量以及任务的一元约束(硬约束或软约束)。域是所有工作时间
一个星期内完成任务,持续时间以小时为单位。天数表示(在输入和输出中)
以字符串“ mon”,“ tue”,“ wed”,“ thu”和“ fri”表示,时间表示为字符串“ 9am”,“ 10am”,
“上午11点”,“下午12点”,“下午1点”,“下午2点”,“下午3点”,“下午4点”和“下午5点”。开始和结束的唯一可能值
任务的结束时间是这些日期和时间的组合,例如“早上9点”。每个任务名称是
一个字符串(无空格),唯一的软约束是软期限约束。
可能的输入(任务和约束)如下:
#二进制约束
约束,ht2i#t1之前的ht1i在t2开始或之前开始
约束,ht2i之后的ht1i#t1在t2结束之后或何时开始
约束,ht1i当日ht2i#t1和t2安排在同一天
约束,ht1i开始于ht2i#t1恰好在t2结束时开始
#硬域约束
域,hti hdayi#t随时在指定日期开始
域,hti htimei#t在任何一天的给定时间开始
域,hti在给定时间或之前在hdayi htimei#之前启动
域,hti开始-在给定时间或之后的hdayi htimei#之后
域,hti在给定时间或之前在hdayi htimei#之前结束
域,hti在给定时间或之后的hdayi htimei#之后结束
域,hti开始于hdayi htimei-hdayi htimei#白天时间范围
域,hti结尾于hdayi htimei-hdayi htimei#白天时间范围
域,hti在任何时间的htimei#之前或之前开始
域,hti在任何时间的htimei#之前或之前结束
域,hti在任何一天的时间或之后的htimei#之后启动
域,hti在任何时间或之后的htimei#之后结束
#软期限限制
域,hti结尾于hdayi htimei hcosti#截止日期每小时的费用
#个任务的名称和持续时间
任务,姓氏hdurationi
要定义解决方案的成本(可能仅部分满足最终期限的约束),请添加
与违反所有任务的软约束相关的成本。令V为变量集
(代表任务),C是所有软截止期限约束的集合。假设这样一个约束
截止日期(dc,tc)和罚款成本costc适用于变量v,并且(dv,tv)为结束日期
解决方案S中v的时间和时间。例如,costc可能是100,而(dv,tv)可能是(mon,5pm)
截止日期(dc,tc)是(mon,3pm);此变量分配的费用为200。
将延迟δ((d1,t1),(d2,t2))定义为(d1,t1)在(d2,t2)之后的小时数
正数,否则为0,一整天为24小时。那么,cv是软截止日期
适用于变量v的约束:
成本(S)= P
cv∈C
costcv ∗δ((dv,tv),(dcv
,电视
))
启发式
在此分配中,您将使用优先级队列对贪婪搜索进行排序,以根据
关于启发式函数h。此函数必须采用任意CSP并返回
从任何状态S到解的距离。因此,与解决方案相比,每个变量v都有关联
带有一组可能的值(当前域)。
启发式估计从给定状态S可以达到的最佳解决方案的成本
假设可以为每个变量分配一个值,该值可以最大程度地减少软期限的成本
适用于该变量的约束。启发式功能会在集合中增加这些最低成本
所有变量中的变量,类似于计算上述解决方案成本的成本。让S成为CSP
变量V并让v的域(写为dom(v))成为v的一组结束日期和时间。然后,
求和在所有软截止期限约束cv上均如上所述:
h(S)= P
cv∈Cmin(dv,tv)∈dom(v)costcv ∗δ((dv,tv),(dcv
,电视
))
Implementation
Put all your code in one Python file called fuzzyScheduler.py. You may (in one or two cases)
copy code from AIPython to fuzzyScheduler.py and modify that code, but do not copy large
amounts of AIPython code. Instead, in preference, write classes in fuzzyScheduler.py that
extend the AIPython classes.
Use the Python code for generic search algorithms in searchGeneric.py. This code includes a
class Searcher with a method search that implements depth-first search using a list (treated
as a stack) to solve any search problem (as defined in searchProblem.py). For this assignment,
modify the AStarSearcher class that extends Searcher and makes use of a priority queue to store
the frontier of the search. Order the nodes in the priority queue based on the cost of the nodes
calculated using the heuristic function.
Use the Python code in cspProblem.py, which defines a CSP with variables, domains and constraints. Add costs to CSPs by extending this class to include a cost and a heuristic function h to
calculate the cost. Also use the code in cspConsistency.py. This code implements the transitions
in the state space necessary to solve the CSP. The code includes a class Search with AC from CSP
that calls a method for domain splitting. Every time a CSP problem is split, the resulting CSPs
are made arc consistent (if possible). Rather than extending this class, you may prefer to write
a new class Search with AC from Cost CSP that has the same methods but implements domain
splitting over constraint optimization problems.
You should submit your fuzzyScheduler.py and any other files from AIPython needed to run
your program (see below). The code in fuzzyScheduler.py will be run in the same directory
as the AIPython files that you submit. Your program should read input from a file passed as an
argument and print output to standard output.
Sample Input
All input will be a sequence of lines defining a number of tasks, binary constraints and domain
constraints, in that order. Comment lines (starting with a ‘#’ character) may also appear in the
file, and your program should be able to process and discard such lines. All input files can be
assumed to be of the correct format – there is no need for any error checking of the input file.
Below is an example of the input form and meaning. Note that you will have to submit at least
three input test files with your assignment. These test files should include one or more comments
to specify what scenario is being tested.
# two tasks with two binary constraints and soft deadlines
task, t1 3
task, t2 4
# two binary constraints
constraint, t1 before t2
constraint, t1 same-day t2
# domain constraint
domain, t2 mon
# soft deadlines
domain, t1 ends-by mon 3pm 10
domain, t2 ends-by mon 3pm 10
Sample Output
Print the output to standard output as a series of lines, giving the start day and time for each task
(in the order the tasks were defined). If the problem has no solution, print ‘No solution’. When
there are multiple optimal solutions, your program should produce one of them. Important: For
auto-marking, make sure there are no extra spaces at the ends of lines, and no extra line at the
end of the output. Set all display options in the AIPython code to 0.
The output corresponding to the above input is as follows:
t1:mon 9am
t2:mon 12pm
cost:10
Submission
• Submit all your files using the following command (this includes relevant AIPython code):
give cs9414 ass1 fuzzyScheduler.py search*.py csp*.py display.py *.txt
• Your submission should include:
– Your .py source file(s) including any AIPython files needed to run your code
– A series of .txt files (at least three) that you have used as input files to test your system
(each including comments to indicate the scenarios tested), and the corresponding .txt
output files (call these input1.txt, output1.txt, input2.txt, output2.txt, etc.);
submit only valid input test files
• When your files are submitted, a test will be done to ensure that your Python files run on
the CSE machine (take note of any error messages printed out)
• Check that your submission has been received using the command:
9414 classrun -check ass1
Assessment
Marks for this assignment are allocated as follows:
• Correctness (auto-marked): 10 marks
• Programming style: 5 marks
Late penalty: 3 marks per day or part-day late off the mark obtainable for up to 3
(calendar) days after the due date.
Assessment Criteria
• Correctness: Assessed on valid input tests as follows (where the input file can have any
name, not just input1.txt, so read the file name from sys.argv[1]):
python3 fuzzyScheduler.py input1.txt > output1.txt
• Programming style: Understandable class and variable names, easy to understand code,
good reuse of AIPython code, adequate comments, suitable test files
Plagiarism
Remember that ALL work submitted for this assignment must be your own work and no code
sharing or copying is allowed. You may use code from the Internet only with suitable attribution
of the source in your program. Do not use public code repositories. All submitted assignments will
be run through plagiarism detection software to detect similarities to other submissions, including
from past years. You should carefully read the UNSW policy on academic integrity and plagiarism
(linked from the course web page), noting, in particular, that collusion (working together on an
assignment, or sharing parts of assignment solutions) is a form of plagiarism. There is also a new
plagiarism policy starting this term with more severe penalties.


EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue


EasyDue™是一个服务全球中国留学生的专业代写公司
专注提供稳定可靠的北美、澳洲、英国代写服务
专注提供CS、统计、金融、经济、数据科学专业的作业代写服务