Instance-Based Parameter Tuningfor

Instance-Based Parameter Tuning
for Evolutionary AI Planning
Mátyás Brendel
Projet TAO, INRIA Saclay & LRI
Université Paris Sud
Orsay, France
[e-mail]
Marc Schoenauer
Projet TAO, INRIA Saclay & LRI
Université Paris Sud
Orsay, France
[e-mail]
ABSTRACT
Learn-and-Optimize (LaO) is a generic surrogate based
method for parameter tuning combining learning and optimization.
In this paper LaO is used to tune Divide-and-
Evolve (DaE), an Evolutionary Algorithm for AI Planning.
The LaO framework makes it possible to learn the relation
between some features describing a given instance and
the optimal parameters for this instance, thus it enables
to extrapolate this knowledge to unknown instances in the
same domain. Moreover, the learned relation is used as a
surrogate-model to accelerate the search for the optimal parameters.
It hence becomes possible to solve intra-domain
and extra-domain generalization in a single framework. The
proposed implementation of LaO uses an Arti_cial Neural
Network for learning the mapping between features and optimal
parameters, and the Covariance Matrix Adaptation
Evolution Strategy for optimization. Results demonstrate
that LaO is capable of improving the quality of the DaE results
even with only a few iterations. The main limitation of
the DaE case-study is the limited amount of meaningful features
that are available to describe the instances. However,
the learned model reaches almost the same performance on
the test instances, which means that it is capable of generalization.
Categories and Subject Descriptors
I.2.6 [Computing Methodologies]: Arti_cial Intelligence
Learning Parameter learning
General Terms
Theory
Keywords
parameter tuning, AI Planning, evolutionary algorithms
1. INTRODUCTION
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
GECCO’11, July 12–16, 2011, Dublin, Ireland.
Copyright 2011 ACM 978-1-4503-0690-4/11/07 ...$10.00.
Parameter tuning is basically a general optimization problem
applied o_-line to _nd the best parameters for complex
algorithms, for example for Evolutionary Algorithms (EAs).
Whereas the e_ciency of EAs has been demonstrated on
several application domains [29, 18], they usually need computationally
expensive parameter tuning. Consequently, one
is tempted to use either the default parameters of the framework
he is using, or parameter values given in the literature
for problems that are similar to his one.
Being a general optimization problem, there are as many
parameter tuning algorithms as optimization techniques [7,
19]. However, several specialized methods have been proposed,
and the most prominent ones today are Racing [5],
REVAC [21], SPO [2], and ParamILS [14]. All these approaches
face the same crucial generalization issue: can a
parameter set that has been optimized for a given problem
be successfully used for another one? The answer of course
depends on the similarity of both problems. However, even
in an optimization domain as precisely de_ned as AI Planning,
there are very few results describing meaningful similarity
measures between problem instances. Moreover, until
now, su_ciently precise and accurate features have not been
speci_ed that would allow the user to accurately describe the
problem, so that the optimal parameter-set could be learned
from this feature-set, and carried on to other problems with
similar description. To the best of our knowledge, no design
of a general learning framework has been proposed, and no
general experiments have been carried out yet with some
representative domains of AI planning.
In the SAT domain, however, one work must be given as an
example of what can be done along those lines. In [13], many
relevant features have been gathered based on half a century
of SAT-research, and hundreds of papers. Extensive parameter
tuning on several thousands of instances has allowed
the authors to learn, using function regression, a meaningful
mapping between the features and the running-time of
a given SAT solver with given parameters. Optimizing this
model makes it possible to choose the optimal parameters
for a given (unknown) instance. The present paper aims at
generalizing this work made in AI planning, with one major
di_erence: the target will be here to optimize the _tness
value for a given runtime, and not the runtime to solution {
as the optimal solution is generally not known for AI planning
problems.
Unfortunately, until now, nobody has yet proposed a set of
features for AI Planning problems in general, that would
be su_cient to describe the characteristics of a problem,
like was done in the SAT domain [13]. This paper makes a
591
step toward a framework for parameter tuning applied generally
to AI Planning and proposes a preliminary set of features.
The Learn-and-Optimize (LaO) framework consists
of the combination of optimizing (i.e., parameter tuning)
and learning, i.e., _nding the mapping between features and
best parameters. Furthermore, the results of learning will already
be useful to further the optimization phases, using the
learned model as in standard surrogate-model based techniques
(see e.g., [1] for a Gaussian-process-based approach).
LaO can of course be applied to any target optimization
methodology that requires parameter tuning. In this paper,
the target optimization technique is an Evolutionary
Algorithm (EA), more precisely the evolutionary AI planner
called Divide-and-Evolve (DaE). However, DaE will be
here considered as a black-box algorithm, without any modi-
_cation for the purpose of this work compared to its original
version described in [17].
The paper is organized as follows: AI Planning Problems are
briey introduced in section 2. Section 3 describes the and
the classical YAHSP solver and the evolutionary Divide-and-
Evolve algorithm. Section 4 introduces the original, top level
parameter tuning method, Learn-and-Optimize. The case
study presented in Section 5 applies LaO to DaE, following
the rules of the International Planning Competition 2011 {
Learning Track. Finally, conclusions are drawn and further
directions of research are proposed in Section 6.
2. AI PLANNING
An Arti_cial Intelligence (AI) planning problem is de_ned
by the triplet of an initial state, a goal state, and a set
of possible actions. An action modi_es the current state
and can only be applied if certain conditions are met. A
solution plan to a planning problem is an ordered list of
actions, whose execution from the initial state achieves the
goal state. The quality criterion of a plan depends on the
type of available actions: in the simplest case (e.g. STRIPS
domain), it is the number of actions; it may also be the
total cost of the pan for actions with cost; and it is the total
duration of the plan, aka makespan, for temporal problems
with so called durative actions.
Domain-independent planners rely on the Planning Domain
De_nition Language PDDL2.1 [8]. The history of PDDL is
closely related to the di_erent editions of the International
Planning Competitions (IPCs http://ipc.icaps-conference.
org/), and the problems submitted to the participants, written
in PDDL, are still the main benchmarks in AI Planning.
The description of a planning problem consists of two separate
parts usually placed in two di_erent _les: the generic
domain on the one hand and a speci_c instance scenario
on the other hand. The domain _le speci_es object types
and predicates, which de_ne possible states, and actions,
which de_ne possible state changes. The instance scenario
declares the actual objects of interest, gives the initial state
and provides a description of the goal. A state is described
by a set of atomic formulae, or atoms. An atom is de-
_ned by a predicate followed by a list of object identi_ers:
(PREDICATE NAME OBJ1 ... OBJN).
The initial state is complete, whereas the goal might be a
partial state. An action is composed of a set of preconditions
and a set of e_ects, and applies to a list of variables given
as arguments, and possibly a duration or a cost. Preconditions
are logical constraints which apply domain predicates
to the arguments and trigger the e_ects when they are satis-
_ed. E_ects enable state transitions by adding or removing
atoms.
A solution plan to a planning problem is a consistent schedule
of grounded actions whose execution in the initial state
leads to a state that contains the goal state, i.e., where all
atoms of the problem goal are true. A planning problem
de_ned on domain D with initial state I and goal G will be
denoted in the following as PD(I;G).
3. DIVIDE-AND-EVOLVE
Early approaches to AI Planning using Evolutionary Algorithms
directly handled possible solutions, i.e. possible
plans: an individual is an ordered sequence of actions see
[25, 20, 27, 28, 6]. However, as it is often the case in Evolutionary
Combinatorial optimization, those direct encoding
approaches have limited performance in comparison to
the traditional AI planning approaches. Furthermore, hybridization
with classical methods has been the way to success
in many combinatorial domains, as witnessed by the
fruitful emerging domain of memetic algorithms [11]. Along
those lines, though relying on an original memetization"
principle, a novel hybridization of Evolutionary Algorithms
(EAs) with AI Planning, termed Divide-and-Evolve (DaE)
has been proposed [23, 24]. For a complete formal description,
see [16].
The basic idea of DaE in order to solve a planning task
PD(I;G) is to _nd a sequence of states S1; : : : ; Sn, and to use
some embedded planner to solve the series of planning problems
PD(Sk; Sk+1), for k 2 [0; n] (with the convention that
S0 =

ผลลัพธ์ (ไทย) 1:

การปรับแต่งพารามิเตอร์ตามอินสแตนซ์การวางแผนไอวิวัฒนาการMátyás Brendelเต่า projet, INRIA Saclay และ LRISud Université ปารีสเซฟ ฝรั่งเศส[e-mail] มาร์คเต่า projet, INRIA Saclay และ LRISud Université ปารีสเซฟ ฝรั่งเศส[e-mail]บทคัดย่อเรียนรู้ และปรับปรุง (ลาว) เป็นตัวแทนทั่วไปที่ใช้วิธีการรวมการเรียนรู้และเพิ่มประสิทธิภาพในการปรับแต่งพารามิเตอร์ในเอกสารนี้ ใช้เลาฟังแบ่ง- และ -พัฒนา (แด), อัลกอริทึมการวิวัฒนาการสำหรับ AI วางแผนการกรอบงานลาวทำให้เรียนรู้ความสัมพันธ์ระหว่างคุณลักษณะบางอย่างของอินสแตนซ์การอธิบาย และพารามิเตอร์เหมาะสมสำหรับอินสแตนซ์นี้ จึงช่วยให้การ extrapolate ความรู้นี้กับอินสแตนซ์ที่ไม่รู้จักในโดเมนเดียวกัน นอกจากนี้ ใช้ความสัมพันธ์ของการเรียนรู้เป็นการตัวแทนแบบจำลองเพื่อเร่งหาพารามิเตอร์เหมาะสมดังนั้นจะสามารถแก้ไขโดเมนภายในและโดเมนเพิ่ม generalization ในกรอบเดียว ที่นำเสนอของลาวใช้ตัว Arti_cial ประสาทเครือข่ายเรียนรู้การแม็ประหว่างคุณลักษณะ และเหมาะสมพารามิเตอร์ และปรับเมตริกซ์ความแปรปรวนร่วมวิวัฒนาการการกลยุทธ์การเพิ่มประสิทธิภาพ แสดงให้เห็นถึงผลลัพธ์ลาวที่มีความสามารถในการปรับปรุงคุณภาพของผลแดแม้จะ มีเพียงกี่ซ้ำ ข้อจำกัดหลักของศึกษากรณีของการแดเป็นจำนวนจำกัดของความหมายที่มีการอธิบายการอินสแตนซ์ อย่างไรก็ตามแบบเรียนรู้ถึงเกือบเดียวกันประสิทธิภาพการทำงานบนการทดสอบกรณี ซึ่งหมายความ ว่า มีความสามารถใน generalizationประเภทและตัวบอกเรื่องI.2.6 [วิธีการใช้งาน]: Arti_cial ปัญญาเรียนรู้เรียนรู้พารามิเตอร์เงื่อนไขทั่วไปทฤษฎีคำสำคัญพารามิเตอร์ที่ปรับแต่ง AI วางแผน อัลกอริทึมเชิงวิวัฒนาการ1. บทนำสิทธิ์ในการทำดิจิตอลหรือสิ่งพิมพ์ทั้งหมดหรือส่วนหนึ่งของงานนี้ใช้ส่วนตัวหรือห้องเรียนได้รับ โดยไม่มีค่าธรรมเนียมที่มีสำเนาไม่ทำ หรือกระจายกำไร หรือประโยชน์ทางการค้า และสำเนาที่หมีนี้ประกาศและอ้างอิงเต็มหน้าแรก การคัดลอกอื่น การประกาศใหม่ การลงรายการบัญชีบนเซิร์ฟเวอร์ หรือกระจายไปยังรายการ ต้องการเฉพาะก่อนสิทธิ์และ/หรือค่าธรรมเนียมGECCO'11, 12 – 16 กรกฎาคม 2554 ดับลิน ไอร์แลนด์ลิขสิทธิ์ 2011 พลอากาศ 978-1-4503-0690-4/11/07... $10.00โดยทั่วไปปรับแต่งพารามิเตอร์เป็นปัญหาทั่วไปประสิทธิภาพสูงสุดใช้ o_ สายการ _nd พารามิเตอร์ที่ดีที่สุดสำหรับคอมเพล็กซ์กระบวน เช่นสำหรับอัลกอริทึมเชิงวิวัฒนาการ (EAs)ในขณะที่ e_ciency ของ EAs ได้ ถูกแสดงบนโดเมนโปรแกรมประยุกต์หลาย [29, 18], พวกเขามักจะต้อง computationallyปรับแต่งพารามิเตอร์ราคาแพง ดังนั้น หนึ่งคืออยากใช้เป็นพารามิเตอร์เริ่มต้นของกรอบเขาใช้ หรือค่าพารามิเตอร์ที่กำหนดในวรรณคดีสำหรับปัญหาที่คล้ายกับของเขาเป็นปัญหาทั่วไปปรับให้เหมาะสม มีมากพารามิเตอร์การปรับอัลกอริทึมเป็นเทคนิคเพิ่มประสิทธิภาพ [719] . อย่างไรก็ตาม วิธีการเฉพาะต่าง ๆ ได้รับการเสนอชื่อและโดดเด่นที่สุดวันนี้มีแข่งรถ [5],REVAC [21], [2] SPO ก ParamILS [14] วิธีเหล่านี้ทั้งหมดเผชิญปัญหา generalization สำคัญเดียวกัน: สามารถเป็นชุดพารามิเตอร์ที่ปรับให้เหมาะสำหรับปัญหาที่กำหนดเสร็จเรียบร้อยใช้อื่น คำตอบของหลักสูตรขึ้นอยู่กับความคล้ายของปัญหาทั้งสอง อย่างไรก็ตาม แม้แต่ในโดเมนเป็น de_ned ได้อย่างแม่นยำว่า AI การวางแผนเพิ่มประสิทธิภาพการมีผลน้อยมากที่อธิบายความคล้ายคลึงกันที่มีความหมายวัดระหว่างอินสแตนซ์ของปัญหา นอกจากนี้ จนกระทั่งตอนนี้ su_ciently คุณลักษณะความ แม่นยำไม่ได้speci_ed ที่จะช่วยให้ผู้ใช้สามารถอธิบายได้ถูกต้องปัญหา เพื่อให้สามารถเรียนชุดพารามิเตอร์ที่เหมาะสมจากนี้ ชุดคุณลักษณะ และจำหน่ายไปยังปัญหาอื่น ๆ ด้วยลักษณะคล้ายกัน กับความรู้ของเรา ไม่ออกของกรอบการเรียนรู้ทั่วไปได้รับการเสนอชื่อ และไม่มีการดำเนินการทดลองทั่วไปออก ยัง มีบางโดเมนที่พนักงานของ AI มีการวางแผนในโดเสาร์ อย่างไรก็ตาม งานหนึ่งต้องได้รับเป็นการตัวอย่างของสิ่งที่สามารถทำได้ตามบรรทัด ใน [13], มากคุณลักษณะที่เกี่ยวข้องได้ถูกรวบรวมขึ้นในครึ่งศตวรรษเสาร์วิจัย และหลายร้อยของเอกสาร พารามิเตอร์อย่างละเอียดปรับแต่งบนอินสแตนซ์หลายพันได้รับอนุญาตผู้เขียนเรียนรู้ ใช้ฟังก์ชันถดถอย การสื่อความหมายการแม็ประหว่างคุณลักษณะและเวลาทำงานของโปรแกรมแก้ปัญหา SAT กำหนดมีกำหนดพารามิเตอร์ เพิ่มประสิทธิภาพนี้รูปแบบทำให้เลือกพารามิเตอร์เหมาะสมสำหรับอินสแตนซ์ (ไม่รู้จัก) กำหนด ปัจจุบันกระดาษมีวัตถุประสงค์งานนี้ทำในการวางแผน มีวิชาหนึ่งอาย generalizingdi_erence: เป้าหมายมีการ ปรับ _tness การค่าการรันไทม์ที่กำหนด ไม่รันไทม์การโซลูชัน{เป็นโซลูชั่นเหมาะสมโดยทั่วไปไม่ทราบสำหรับ AI วางแผนปัญหาอับ จนถึงขณะนี้ ไม่มีใครได้ยังนำเสนอชุดของลักษณะปัญหา AI วางแผนทั่วไป ที่ต้องมี su_cient เพื่ออธิบายลักษณะของปัญหาต้องไม่ทำในโดเสาร์ [13] ทำให้เอกสารนี้เป็น591ใช้ขั้นตอนกรอบงานสำหรับการปรับแต่งพารามิเตอร์ทั่วไปการวางแผนไอ และเสนอชุดคุณลักษณะเบื้องต้นประกอบด้วยกรอบการเรียนรู้ และปรับปรุง (ลาว)ของการรวมกันของประสิทธิภาพสูงสุด (พารามิเตอร์เช่น ปรับแต่ง)และเรียน รู้ เช่น _nding การแม็ประหว่างคุณลักษณะ และพารามิเตอร์ที่ดีที่สุด นอกจากนี้ ผลการเรียนรู้จะเรียบร้อยเป็นประโยชน์เพิ่มเติมขั้นตอนเพิ่มประสิทธิภาพ การใช้รูปแบบการเรียนรู้ในมาตรฐานตัวแทนแบบจำลองโดยใช้เทคนิค(ดูเช่น, [1] เป็น Gaussian-กระบวนการปฏิบัติตาม)ลาวแน่นอนใช้ปรับเป้าหมายใด ๆวิธีที่ต้องการปรับแต่งพารามิเตอร์ ในเอกสารนี้เทคนิคเพิ่มประสิทธิภาพเป้าหมายมีการ Evolutionaryอัลกอริทึม (EA), ได้แม่นยำมากวิวัฒนาการ AI วางแผนการเรียกว่าแบ่ง และพัฒนา (แด) อย่างไรก็ตาม แดจะที่นี่ถือว่าเป็นกล่องดำอัลกอริทึม โดย modi ใด ๆ -_cation เพื่อทำงานนี้เมื่อเทียบกับเดิมรุ่นที่ระบุไว้ใน [17]จัดกระดาษเป็นดังนี้: มีปัญหาการวางแผนไอbriey ที่แนะนำในส่วนที่ 2 หมวดที่ 3 อธิบายการ และโปรแกรมแก้ปัญหา YAHSP คลาสสิกและแบ่งวิวัฒนาการ- และ -พัฒนาอัลกอริทึม ส่วน 4 ระดับเดิม สูงสุดที่แนะนำวิธี เรียนรู้ และเพิ่มประสิทธิภาพการปรับแต่งพารามิเตอร์ กรณีและปัญหาศึกษาที่นำเสนอใน 5 ส่วนใช้ลาวแด ต่อไปนี้กฎของ{2011 การแข่งขันนานาชาติวางแผนเรียนรู้ติดตาม ในที่สุด ถูกวาด และเพิ่มเติมมีการนำเสนอทิศทางงานวิจัยใน 6 ส่วน2. AI วางแผนการ Arti_cial Intelligence (AI) การวางแผนปัญหาคือ de_nedโดย triplet เป็นสถานะเริ่มต้น สถานะเป้าหมาย และชุดของการดำเนินการได้ Modi_es ดำเนินการสถานะปัจจุบันและสามารถจะใช้ถ้าตรงตามเงื่อนไขบางอย่าง Aรายการสินค้ามีแผนแก้ปัญหาปัญหาวางแผนการดำเนินการ การได้รับซึ่งการดำเนินการจากสถานะเริ่มต้นสถานะเป้าหมาย ขึ้นอยู่กับเกณฑ์คุณภาพของแผนการประเภทของงาน: ในกรณีที่ง่ายที่สุด (เช่นแถบโดเมน), เป็นหมายเลขของการดำเนินการ นอกจากนี้ยังอาจจะต้นทุนรวมของแพนสำหรับการดำเนินการกับต้นทุน และผลรวมระยะเวลาของแผน aka makespan ปัญหาชั่วคราวมีสิ่งที่เรียกว่าการดำเนินการ durativeใช้วางแผนอิสระโดเมนโดเมนการวางแผนภาษา De_nition PDDL2.1 [8] ประวัติของ PDDLสัมพันธ์ใกล้ชิดกับรุ่น di_erent ที่ประเทศวางแผนการแข่งขัน (IPCs http://ipc.icaps-conferenceองค์กร /), และปัญหาที่ส่งผู้เข้าร่วม เขียนใน PDDL ได้ยังเกณฑ์มาตรฐานหลักในการวางแผนไอคำอธิบายของปัญหาในการวางแผนประกอบด้วยสองส่วนที่มักจะอยู่ใน _les di_erent สอง: ทั่วไปโดเมนสถานการณ์สมมติตัวอย่าง speci_c และมือหนึ่งในทางตรงข้าม Speci_es _le โดเมนวัตถุชนิดและเพรดิเคต สุด de_ne ที่อเมริกา และการดำเนินการเปลี่ยนสถานะได้ที่ de_ne ตัวอย่างสถานการณ์ประกาศวัตถุจริงที่น่าสนใจ ทำให้สถานะเริ่มต้นรวมทั้งคำอธิบายของเป้าหมาย อธิบายรัฐโดยชุดของสูตรอะตอม อะตอม อะตอมจะเดอ-_ned โดยเพรดิเคตการตามรายการของวัตถุ identi_ers:(ชื่อบท OBJ1... OBJN)สถานะเริ่มต้นเสร็จสมบูรณ์ ในขณะที่เป้าหมายอาจเป็นรัฐบางส่วน การดำเนินการประกอบด้วยชุดของเงื่อนไขเบื้องต้นและชุดของ e_ects และใช้กับรายการของตัวแปรที่กำหนดเป็น อาร์กิวเมนต์ และอาจรวมถึงระยะเวลา หรือต้นทุน เงื่อนไขเบื้องต้นมีข้อจำกัดทางตรรกะที่ใช้เพรดิเคตของโดเมนอาร์กิวเมนต์และทริกเกอร์ e_ects เมื่อ satis-_ed. E_ects เปลี่ยนสถานะเปิดใช้งาน โดยการเพิ่ม หรือเอาออกอะตอมแผนการแก้ปัญหาปัญหาการวางแผนเป็นเวลาสอดคล้องกันการป่นเล็กน้อยซึ่งการดำเนินการในสถานะเริ่มต้นนำไปสู่รัฐที่ประกอบด้วยสถานะเป้าหมาย เช่น ซึ่งทั้งหมดอะตอมของเป้าหมายปัญหาเป็นจริง ปัญหาวางแผนde_ned บนโดเมน D กับฉันและเป้าหมาย G จะเป็นสถานะเริ่มต้นสามารถบุในต่อไปนี้เป็น PD (I G)3. แบ่ง และพัฒนาแนวช่วง AI วางแผนโดยใช้อัลกอริทึมเชิงวิวัฒนาการจัดการปัญหา เช่นได้โดยตรงแผน: บุคคลเป็นลำดับการสั่งการดำเนินการของ[25, 20, 27, 28, 6] อย่างไรก็ตาม มันมักจะเป็นกรณีใน Evolutionaryเพิ่มประสิทธิภาพปัญหา ผู้ตรงเข้าวิธีมีจำกัดประสิทธิภาพเปรียบเทียบแบบ AI วางแผนวิธีการ นอกจากนี้ hybridizationวิธีคลาสสิกที่ได้รับวิธีสู่ความสำเร็จในหลายปัญหาโดเมน เป็น witnessed โดยโดเมนเกิดประสบของอัลกอริทึมขั้น [11] ตามบรรทัดเหล่านั้น แต่ อาศัยอยู่ใน memetization เดิม"หลัก hybridization นวนิยายของอัลกอริทึมเชิงวิวัฒนาการ(EAs) กับ AI วางแผน เรียกว่าแบ่ง และพัฒนา (แด)ได้รับการเสนอชื่อ [23, 24] สำหรับคำอธิบายอย่างสมบูรณ์ดู [16]ความคิดพื้นฐานของแดการงานการวางแผนPD (I G) จะ _nd ลำดับของอเมริกา S1 : : : ; Sn และ การใช้วางแผนบางอย่างฝังตัวเพื่อแก้ไขชุดปัญหาวางแผนPD (Sk Sk + 1), สำหรับ k 2 [0; n] (มีการประชุมที่S0 =

ผลลัพธ์ (ไทย) 2:

อินสแตนซ์ที่ใช้ปรับแต่งพารามิเตอร์
วิวัฒนาการ AI วางแผน
Mátyás Brendel
Projet TAO, INRIA ซาเคลย์และ LRI
Université Paris Sud
Orsay, ฝรั่งเศส
[e-mail]
มาร์ค Schoenauer
Projet TAO, INRIA ซาเคลย์และ LRI
Université Paris Sud
Orsay, ฝรั่งเศส
marc.schoenauer @ inria.fr
บทคัดย่อ
เรียนรู้และเพิ่มประสิทธิภาพ (ลาว) เป็นตัวแทนทั่วไปตาม
วิธีการปรับแต่งพารามิเตอร์การรวมการเรียนรู้และการเพิ่มประสิทธิภาพ.
ในกระดาษนี้ลาวจะใช้ในการปรับแต่ง Divide-and-
วิวัฒนาการ (DAE) วิวัฒนาการขั้นตอนวิธีการวางแผน AI
กรอบลาวทำให้มันเป็นไปได้ที่จะเรียนรู้ความสัมพันธ์
ระหว่างคุณสมบัติบางอย่างที่อธิบายตัวอย่างที่กำหนดและ
พารามิเตอร์ที่เหมาะสมที่สุดสำหรับกรณีนี้จึงช่วยให้
การคาดการณ์ความรู้ในการกรณีที่ไม่รู้จักนี้ใน
โดเมนเดียวกัน นอกจากนี้ยังมีความสัมพันธ์ที่ได้เรียนรู้ที่จะใช้เป็น
ตัวแทนรุ่นเพื่อเร่งค้นหาสำหรับพารามิเตอร์ที่เหมาะสม.
มันจึงเป็นไปได้ที่จะแก้โดเมนภายใน
และลักษณะทั่วไปเป็นพิเศษโดเมนในกรอบเดียว
การดำเนินการเสนอลาวใช้ประสาท Arti_cial
เครือข่ายสำหรับการเรียนรู้การทำแผนที่ระหว่างคุณสมบัติและดีที่สุด
พารามิเตอร์และแปรปรวนเมทริกซ์ปรับ
กลยุทธ์วิวัฒนาการในการเพิ่มประสิทธิภาพ แสดงให้เห็นถึงผล
ที่ลาวมีความสามารถในการปรับปรุงคุณภาพของแดส่งผลให้
แม้จะมีเพียงไม่กี่ซ้ำ ข้อ จำกัด หลักของ
แดกรณีศึกษาเป็นจำนวนเงินที่ จำกัด ของคุณสมบัติที่มีความหมาย
ที่มีอยู่เพื่ออธิบายกรณี อย่างไรก็ตาม
รูปแบบการเรียนรู้ถึงผลการดำเนินงานเกือบเหมือนกันใน
กรณีการทดสอบซึ่งหมายความว่ามันเป็นความสามารถในการทั่วไป.
หมวดหมู่และอธิบายเรื่อง
I.2.6 [วิธีคอมพิวเตอร์]: Arti_cial หน่วยสืบราชการลับ
การเรียนรู้การเรียนรู้พารามิเตอร์
เงื่อนไขทั่วไป
ทฤษฎี
คำ
พารามิเตอร์ปรับ AI วางแผน อัลกอริทึมวิวัฒนาการ
1 บทนำ
อนุญาตให้ทำสำเนาดิจิตอลหรือหนักของทั้งหมดหรือบางส่วนของการทำงานในการนี้
การใช้งานส่วนตัวหรือห้องเรียนจะได้รับโดยไม่เสียค่าธรรมเนียมให้สำเนาจะ
ไม่ได้ทำหรือการกระจายเพื่อหากำไรหรือประโยชน์ในเชิงพาณิชย์และที่สำเนา
แบกนี้และแจ้งให้ทราบล่วงหน้าอ้างอิงเต็มรูปแบบครั้งแรก หน้า ในการคัดลอกอย่างอื่นเพื่อ
เผยแพร่โพสต์บนเซิร์ฟเวอร์หรือเพื่อแจกจ่ายไปยังรายการที่ต้องการที่เฉพาะเจาะจงก่อน
ได้รับอนุญาตและ / หรือค่าธรรมเนียม.
GECCO'11, 12-16 กรกฎาคม 2011, ดับลินไอร์แลนด์.
สงวนลิขสิทธิ์ พ.ศ. 2011 พลอากาศเอก 978-1-4503 -0690-4 / 7/11 ... $ 10.00.
การปรับแต่งพารามิเตอร์นั้นเป็นปัญหาการเพิ่มประสิทธิภาพทั่วไป
ใช้ o_ บรรทัด _nd พารามิเตอร์ที่ดีที่สุดสำหรับซับซ้อน
ขั้นตอนวิธีการเช่นวิวัฒนาการอัลกอริทึม (EAs).
ในขณะที่ e_ciency ของ EAs ที่ได้รับ แสดงให้เห็นถึง
การประยุกต์ใช้โดเมนหลาย [29, 18] พวกเขามักจะต้องคำนวณ
ค่าพารามิเตอร์การปรับแต่งที่มีราคาแพง ดังนั้นหนึ่ง
คืออยากจะใช้ค่าเริ่มต้นของกรอบ
เขาใช้หรือค่าพารามิเตอร์ที่กำหนดในวรรณคดี
สำหรับปัญหาที่คล้ายกับเขา.
เป็นปัญหาการเพิ่มประสิทธิภาพโดยทั่วไปมีเป็นจำนวนมาก
ขั้นตอนวิธีการปรับแต่งพารามิเตอร์เป็นเทคนิคการเพิ่มประสิทธิภาพ [7,
19] อย่างไรก็ตามวิธีการเฉพาะหลายคนได้รับการเสนอชื่อ
และเป็นคนที่โดดเด่นที่สุดในวันนี้จะแข่ง [5],
Revac [21], SPO [2] และ ParamILS [14] ทุกวิธีการเหล่านี้
ต้องเผชิญกับปัญหาทั่วไปที่สำคัญเหมือนกัน: สามารถ
ตั้งค่าพารามิเตอร์ที่ได้รับการปรับให้เหมาะสมกับปัญหาที่กำหนด
ใช้ประสบความสำเร็จสำหรับอีกคนหนึ่ง? คำตอบที่แน่นอน
ขึ้นอยู่กับความคล้ายคลึงกันของปัญหาทั้งสอง อย่างไรก็ตามแม้
ในโดเมนเพิ่มประสิทธิภาพ de_ned แม่นยำเป็น AI วางแผน
มีผลน้อยมากที่มีความหมายคล้ายคลึงกันอธิบาย
มาตรการระหว่างกรณีปัญหาที่เกิดขึ้น ยิ่งไปกว่านั้นจนถึง
ตอนนี้ su_ciently คุณสมบัติแม่นยำและถูกต้องไม่ได้รับการ
speci_ed ที่จะช่วยให้ผู้ใช้ที่จะต้องอธิบาย
ปัญหาที่เกิดขึ้นเพื่อให้เหมาะสมที่สุดพารามิเตอร์ที่ตั้งไว้อาจจะได้เรียนรู้
จากคุณลักษณะชุดนี้และดำเนินการเกี่ยวกับการแก้ไขปัญหาอื่น ๆ ที่มี
คำอธิบายที่คล้ายกัน . ที่ดีที่สุดของความรู้ของเราไม่มีการออกแบบ
ของกรอบการเรียนรู้ทั่วไปได้รับการเสนอและไม่มี
การทดลองทั่วไปได้รับการดำเนินการยังมีบางส่วน
โดเมนตัวแทนของการวางแผนไอ.
ในโดเมน SAT แต่หนึ่งในการทำงานจะต้องได้รับในฐานะที่เป็น
ตัวอย่าง ของสิ่งที่สามารถทำได้ตามเส้นที่ ใน [13] หลาย
คุณสมบัติที่เกี่ยวข้องได้รับการรวบรวมอยู่บนพื้นฐานของครึ่งศตวรรษ
ของ SAT-วิจัยและร้อยของเอกสาร พารามิเตอร์ที่กว้างขวาง
การปรับแต่งหลายต่อหลายพันกรณีได้รับอนุญาตให้
เขียนในการเรียนรู้โดยใช้ฟังก์ชั่นการถดถอย, ความหมาย
การทำแผนที่ระหว่างคุณสมบัติและการทำงานเวลา
แก้ SAT รับกับพารามิเตอร์ที่กำหนด การเพิ่มประสิทธิภาพนี้
รูปแบบจะทำให้มันเป็นไปได้ที่จะเลือกพารามิเตอร์ที่เหมาะสมที่สุด
สำหรับการได้รับ (ไม่ทราบ) เช่น มีจุดมุ่งหมายที่กระดาษในปัจจุบันที่
generalizing งานนี้ทำในการวางแผน AI กับหนึ่งที่สำคัญ
di_erence: เป้าหมายจะอยู่ที่นี่เพื่อเพิ่มประสิทธิภาพ _tness
ค่าสำหรับรันไทม์ที่กำหนดและไม่ได้ใช้งานจริงเพื่อแก้ปัญหา {
เป็นทางออกที่ดีที่สุดโดยทั่วไปไม่เป็นที่รู้จักสำหรับ AI การวางแผน
ปัญหา.
แต่น่าเสียดายที่จนถึงขณะนี้ไม่มีใครได้เสนอยังชุดของ
คุณสมบัติสำหรับ AI ปัญหาการวางแผนโดยทั่วไปที่จะ
ได้รับการ su_cient เพื่ออธิบายลักษณะของปัญหาที่
เหมือนได้ทำในโดเมน SAT [13] กระดาษนี้จะทำให้
591
ขั้นตอนต่อกรอบการทำงานสำหรับการปรับแต่งพารามิเตอร์ที่ใช้โดยทั่วไป
ในการวางแผนและ AI เสนอชุดของคุณสมบัติเบื้องต้น.
เรียนรู้และเพิ่มประสิทธิภาพ (ลาว) ประกอบด้วยกรอบ
ของการรวมกันของการเพิ่มประสิทธิภาพ (เช่นการปรับแต่งพารามิเตอร์)
และการเรียนรู้ เช่นการทำแผนที่ _nding ระหว่างคุณสมบัติและ
พารามิเตอร์ที่ดีที่สุด นอกจากนี้ผลของการเรียนรู้ที่มีอยู่แล้วจะ
เป็นประโยชน์ในการส่งเสริมการเพิ่มประสิทธิภาพขั้นตอนโดยใช้
รูปแบบการเรียนรู้ที่เป็นตัวแทนในมาตรฐานตามรูปแบบเทคนิค
(ดูเช่น [1] สำหรับ Gaussian กระบวนการที่ใช้วิธีการ).
ลาวสามารถของหลักสูตรจะ นำไปใช้ในการเพิ่มประสิทธิภาพเป้าหมายใด ๆ
วิธีการที่ต้องมีการปรับแต่งพารามิเตอร์ ในบทความนี้
เทคนิคการเพิ่มประสิทธิภาพเป้าหมายเป็นวิวัฒนาการ
ขั้นตอนวิธี (EA) อย่างแม่นยำมากขึ้นวางแผน AI วิวัฒนาการ
ที่เรียกว่าแบ่งและวิวัฒนาการ (DAE) อย่างไรก็ตามแดจะได้รับการ
พิจารณาที่นี่เป็นอัลกอริทึมกล่องดำโดยไม่ต้องมี modi-
_cation เพื่อจุดประสงค์ของงานนี้เมื่อเทียบกับเดิม
. รุ่นที่อธิบายไว้ใน [17]
กระดาษมีการจัดระเบียบดังต่อไปนี้: AI ปัญหาการวางแผนมี
การแนะนำใน Briey ส่วนที่ 2 ส่วนที่ 3 อธิบายและ
แก้ YAHSP คลาสสิกและแบ่ง-and-วิวัฒนาการ
ขั้นตอนวิธีการวิวัฒนาการ หมวดที่ 4 การแนะนำเดิมที่ระดับบนสุดของ
วิธีการปรับแต่งพารามิเตอร์เรียนรู้และเพิ่มประสิทธิภาพ กรณี
ศึกษาที่นำเสนอในมาตรา 5 ใช้ลาวแดตาม
กฎของการแข่งขันการวางแผนนานาชาติ 2011 {
ติดตามการเรียนรู้ สุดท้ายได้ข้อสรุปจะมีการวาดและต่อ
ทิศทางของการวิจัยจะนำเสนอในมาตรา 6
2 AI วางแผน
Arti_cial หน่วยสืบราชการลับ (AI) ปัญหาการวางแผน de_ned
โดยแฝดของสถานะเริ่มต้นของรัฐเป้าหมายและชุด
ของการกระทำที่เป็นไปได้ การกระทำ modi_es สถานะปัจจุบัน
และสามารถนำไปใช้ถ้าเงื่อนไขตรง
แผนวิธีการแก้ปัญหาการวางแผนเป็นรายการสั่งซื้อของ
การกระทำที่มีการดำเนินการจากสถานะเริ่มต้นประสบความสำเร็จใน
เป้าหมายของรัฐ เกณฑ์คุณภาพของแผนขึ้นอยู่กับ
ประเภทของการกระทำที่มี: ในกรณีที่ง่าย (เช่นแถบ
โดเมน) มันเป็นจำนวนของการกระทำนั้น มันก็อาจจะ
มีค่าใช้จ่ายรวมของกระทะสำหรับการกระทำที่มีค่าใช้จ่าย; และมันก็เป็นรวม
ระยะเวลาของแผนอาคา makespan สำหรับปัญหาที่เกิดขึ้นชั่วขณะ
ที่มีการกระทำที่เรียกว่า durative.
วางแผนโดเมนอิสระพึ่งพาการวางแผนโดเมน
De_nition ภาษา PDDL2.1 [8] ประวัติศาสตร์ของ PDDL เป็น
อย่างใกล้ชิดที่เกี่ยวข้องกับรุ่น di_erent ของนานาชาติ
การแข่งขันการวางแผน (IPCs http:. //ipc.icaps-conference
org /) และปัญหาที่ส่งไปยังผู้เข้าร่วมที่เขียน
ใน PDDL ยังคงมาตรฐานหลักใน . ไอวางแผน
รายละเอียดของปัญหาการวางแผนประกอบด้วยสองแยก
ชิ้นส่วนที่มักจะวางไว้ในสอง di_erent _les: ทั่วไป
โดเมนบนมือข้างหนึ่งและสถานการณ์เช่น speci_c
ในมืออื่น ๆ โดเมน _le speci_es ประเภทวัตถุ
และภาคซึ่ง de_ne รัฐที่เป็นไปได้และการกระทำ
ซึ่ง de_ne การเปลี่ยนแปลงสถานะที่เป็นไปได้ สถานการณ์เช่น
ประกาศวัตถุที่เกิดขึ้นจริงที่น่าสนใจให้สถานะเริ่มต้น
และให้รายละเอียดของเป้าหมาย รัฐอธิบายไว้
โดยชุดของสูตรอะตอมหรืออะตอม อะตอม de-
_ned โดยสรุปตามด้วยรายการของวัตถุ identi_ers:
. (กริยาชื่อ obj1 ... OBJN)
สถานะเริ่มต้นจะเสร็จสมบูรณ์ในขณะที่เป้าหมายอาจจะมี
บางส่วนของรัฐ การกระทำที่ประกอบด้วยชุดของปัจจัยพื้นฐาน
และชุดของ e_ects และนำไปใช้กับรายชื่อของตัวแปรที่กำหนด
เป็นข้อโต้แย้งและอาจระยะเวลาหรือค่าใช้จ่าย เงื่อนไข
ข้อ จำกัด ตรรกะที่ใช้ภาคโดเมน
ที่จะมีปากเสียงและเรียก e_ects เมื่อพวกเขาพึงพอใจใน
_ed E_ects ช่วยให้การเปลี่ยนสถานะโดยเพิ่มหรือลบ
อะตอม.
แผนแก้ปัญหาในการแก้ไขปัญหาการวางแผนเป็นช่วงเวลาที่สอดคล้องกัน
ของการกระทำที่มีเหตุผลที่มีการดำเนินการอยู่ในสถานะเริ่มต้น
นำไปสู่รัฐที่มีเป้าหมายของรัฐคือการที่ทุก
อะตอมเป้าหมายที่มีปัญหา จริง ปัญหาการวางแผน
de_ned บนโดเมน D กับสถานะเริ่มต้นและเป้าหมายของผม G จะถูก
แสดงในต่อไปนี้เป็น PD. (ฉัน; G)
3 แบ่ง-AND-EVOLVE
ต้นวิธีการวางแผนการใช้ไอวิวัฒนาการขั้นตอนวิธี
การจัดการโดยตรงโซลูชั่นที่เป็นไปได้คือเป็นไปได้ที่
แผน: บุคคลเป็นลำดับของการกระทำที่เห็น
[25, 20, 27, 28, 6] อย่างไรก็ตามในขณะที่มันมักจะเป็นกรณีในวิวัฒนาการ
การเพิ่มประสิทธิภาพ Combinatorial ผู้เข้ารหัสโดยตรง
วิธีการได้รับการ จำกัด ผลการดำเนินงานในการเปรียบเทียบกับ
การวางแผนแบบดั้งเดิม AI วิธี นอกจากนี้การผสมพันธุ์
ด้วยวิธีการคลาสสิกที่ได้รับวิธีการที่จะประสบความสำเร็จ
ในโดเมน combinatorial จำนวนมากเท่าที่เห็นจาก
โดเมนที่เกิดขึ้นใหม่มีผลของขั้นตอนวิธี memetic [11] พร้อม
เส้นที่แม้ว่าจะอาศัยเดิม memetization "
หลักการผสมพันธุ์นวนิยายของอัลกอริทึมวิวัฒนาการ
(EAs) กับเอไอวางแผนเรียกว่าแบ่งและวิวัฒนาการ (DAE)
ได้รับการเสนอ [23 24]. สำหรับคำอธิบายอย่างเป็นทางการที่สมบูรณ์ ,
. ดู [16]
แนวคิดพื้นฐานของ DAE เพื่อที่จะแก้งานวางแผน
PD (ฉัน; G) คือการ _nd ลำดับของรัฐ S1;:::; Sn และใช้งาน
บางอย่างที่ฝังวางแผนในการแก้ชุดของ ปัญหาการวางแผน
PD (Sk; Sk + 1) สำหรับ 2 k [0; n] (ที่มีการประชุมที่
S0 =

ผลลัพธ์ (ไทย) 3:

ตัวอย่างการปรับค่าพารามิเตอร์พื้นฐานสำหรับการวางแผน

วิวัฒนาการไอ M . kgm ไท . kgm s เบรนเดล
โครงการเต๋า inria saclay & lri
มหาวิทยาลัยจากปารีสซูด
ออเซ ฝรั่งเศส
Matthias . เบรนเดล @ lri . fr

มาร์ค schoenauer โครงการเต๋า inria saclay & lri
มหาวิทยาลัยจากปารีสซูด

ออเซ ฝรั่งเศส มาร์ค schoenauer @ inria . fr

เรียนนามธรรมและเพิ่มประสิทธิภาพ ( ลาว ) เป็นตัวแทนจาก
ทั่วไปวิธีสำหรับการปรับแต่งรวมการเรียนรู้และเพิ่มประสิทธิภาพของพารามิเตอร์ ในกระดาษนี้
ลาวจะใช้เพื่อปรับแต่งและแบ่ง -
คาย ( แด ) เป็นขั้นตอนวิธีเชิงวิวัฒนาการสำหรับ AI การวางแผน .
กรอบลาวทำให้มันเป็นไปได้ที่จะเรียนรู้ความสัมพันธ์ระหว่างคุณลักษณะบางอย่างที่อธิบายให้

ตัวอย่างและพารามิเตอร์ที่ดีที่สุดสำหรับอินสแตนซ์นี้จึง เพื่อขยายผลความรู้นี้ช่วยให้

ในกรณีที่ไม่รู้จักเดียวกันกับโดเมน นอกจากนี้ ยังได้เรียนรู้เกี่ยวกับใช้เป็น
นางแบบตัวแทนเร่งค้นหาค่าพารามิเตอร์ที่เหมาะสมที่สุด มันจึงกลายเป็นไปได้ที่จะแก้ปัญหา

เมนภายในและการเพิ่มโดเมนในกรอบเดียว การนำเสนอของลาวใช้เครือข่ายประสาท

arti_cial เรียนรู้การทำแผนที่ระหว่างคุณลักษณะและพารามิเตอร์ที่เหมาะสม
,และความแปรปรวนร่วมแบบการปรับตัว
วิวัฒนาการกลยุทธ์การเพิ่มประสิทธิภาพ ผลลัพธ์ที่แสดงให้เห็นถึง
ที่ลาว สามารถปรับปรุงคุณภาพของแดผลลัพธ์
แม้มีเพียงไม่กี่รอบ . ข้อจำกัดหลักของกรณีศึกษา
แดจำกัดความหมายคุณลักษณะ
ที่มีอยู่เพื่ออธิบายกรณี อย่างไรก็ตาม เรียนรู้รูปแบบ
ถึงเกือบเดียวกันการปฏิบัติ
กรณีทดสอบซึ่งหมายความว่ามันมีความสามารถในการ .
หมวดหมู่และหัวข้อใน
i.2.6 [ คอมพิวเตอร์ ] : วิธีการ arti_cial สติปัญญาการเรียนรู้การเรียนรู้

ค่า


คำหลักทฤษฎีเงื่อนไข การปรับค่าพารามิเตอร์ทั่วไป , ไอ การวางแผน คนแรกของหัวใจ คนสุดท้ายของชีวิต
1 บทนำ
ขออนุญาตให้ดิจิตอลหรือยากคัดลอกทั้งหมดหรือบางส่วนของงานนี้
ใช้ส่วนตัวหรือในชั้นเรียนจะได้รับโดยไม่เสียค่าธรรมเนียมให้เสมือน
ไม่ได้หรือจำหน่ายกำไรหรือประโยชน์เชิงพาณิชย์ และสำเนา
หมีแจ้งให้ทราบนี้และการอ้างอิงเต็มในหน้าแรก เพื่อคัดลอกหรือ

พิมพ์เพื่อโพสต์บนเซิร์ฟเวอร์หรือเพื่อแจกจ่ายไปยังรายการที่ต้องการก่อนได้รับอนุญาตเฉพาะและ / หรือค่า
.
gecco ' 11 , 12 กรกฎาคม– 16 , 2011 , ดับลิน , ไอร์แลนด์ .