COURSE SYLLABUS AND OUTLINE
SWENG 597D.301
SPECIAL TOPICS: SOFT COMPUTING
|
Walter Cedeño |
Fall II, 2006 |
|
Tuesdays & Thursdays 6-9pm |
Penn State, Great Valley |
|
(610) 458-5264 (W) |
(610) 648-3277 |
The purpose of this course is to introduce the students to metaheuristics techniques. A metaheuristic technique is a top-level general strategy which guides other heuristics to search for feasible solutions in complex solution spaces. Metaheuristics have been generally applied to problems classified as NP-Hard or NP-Complete by the theory of computational complexity. However, metaheuristics would also be applied to other combinatorial optimization problems for which it is known that a polynomial-time solution exists but is not practical.
A number of metaheuristics techniques using single solutions or sets of solutions will be described. The course will give emphasis to Swarm Intelligence (SI) techniques and their applications to combinatorial optimization problems in science and engineering. SI techniques are population based stochastic methods where the collective behavior of unsophisticated individuals interact locally with their environment causing the emergence of coherent functional global patterns. Some of the metaheuristics techniques to be described in class includes;
- Particle Swarms
- Ant Colony
- Genetic Algorithms
- Memetic Algorithms
- Simulated Annealing
- Tabu Search
- Greedy Randomized Adaptive Search Procedure
- Variable Neighborhood Search
- Scatter Search
- Guided Local Search & Fast Local Search
- Cellular Automata
- Immune Systems
The students will learn how to apply these techniques to problems in science
and engineering. In addition, population based stochastic techniques will be
compared and contrasted to other techniques in order to identify the advantages
and disadvantages they provide.
The course will consist of lecture, demos, and paper reviews. Lectures will serve as the vehicle to introduce new information to the students. Demos will be use to enforced the material given in lectures and to show work from researchers in the field. Paper reviews will be use to investigate the application of metaheuristics techniques to practical problems. Participation is encouraged during the class.
As part of the course, the students will work on a project with the goal of applying a metaheuristic technique to a combinatorial optimization problem. Teams of two or three students will be created for each project. During the second part of the course, each team will provide an informal description of the problem and how the team plans to solve it using metaheuristics. This exercise will help the team gain a better understanding on how to apply a metaheuristic technique to the problem. Input from the class will provide the team with valuable ideas for the project and potentially provide other ways to apply the technique to the problem.
Optional Textbook:
Other References (A copy should be available in the library):
The outline of the course is as follows:
Day 1: Introduction to Metaheuristics and Swarm Intelligence
(Chapter 1, Chapter 2 pgs 48-55,
64-75)
Introduction to Probability and
Statistics
Day 2: Particle Swarms
(Chapter 7, Chapter 8)
Day 3: Ant Colony Optimization
Project Topic Oral Presentation
Day 4: Genetic Algorithms
(Chapter 4)
Day 5: Memetic Algorithms
(Chapter 5, pgs 245-254)
Project Round Table
Day 6: Simulated Annealing
Midterm Review
Day 7: Midterm
Project Round Table
Day 8: Tabu Search
Day 9: Greedy Randomized Adaptive Search Procedure
Project Round Table
Day 10: Variable Neighborhood Search & Scatter Search
Day 11: Guided Local Search & Fast Local Search
Project Round Table
Day 12: Cellular Automata & Artificial Immune Systems
Day 13: Oral Presentations & Competition
Day 14: Final (Projects Due)
Tools and demo applications to be use in class.
"Academic integrity is the pursuit of scholarly activity free from fraud and deception and is an educational objective of this institution. Academic dishonesty includes, but is not limited to, cheating, plagiarizing, fabricating of information or citations, facilitating acts of academic dishonesty by others, having unauthorized possession of examinations, submitting work for another person or work previously used without informing the instructor, or tampering with the academic work of other students. At the beginning of each course it is responsibility of the instructor to provide a statement clarifying the application of academic integrity to that course". (1989-90 Policies and Rules for Students, p.25).
DISABILITY STATEMENT:
The Pennsylvania State University encourages qualified persons with disabilities to participate in its programs and activities. If you anticipate needing any type of accommodation or have questions about the physical access provided, please contact Kathy Mingioni at 610-648-3315 in advance of your participation or visit.
SECURITY PLAN:
In the event of an emergency of any kind, you are advised to proceed to an agreed upon meeting point in a safer location - probably in the car park area. If you need special consideration in evacuating the classroom, please inform your instructor who will attempt to accommodate your special needs.
Emergency Evacuation Exercises or Actual Emergency Events:
Periodic fire/evacuation exercises are conducted in all occupied PSU Great Valley buildings. Every PSU Great Valley faculty, staff, and student is expected to exit the building and remain outside until the drill or actual event is completed. Drills are a safe opportunity to test the building emergency plan, insure that the fire alarm is working properly, and allows every employee a chance to experience the procedures.
Guidelines in the Event of a Drill or Emergency:
