Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Application of Machine Learning techniques to Optimization algorithms
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Optimization and Systems Theory.
2017 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Applikation av maskininlärning till optimerings algoritmer (Swedish)
Abstract [en]

Optimization problems have been immuned to any attempt of combination with machine learning until a decade ago but it is now an active research field. This thesis has studied the potential implementation of a machine learning heuristic to improve the resolution of the optimization scheduling problems based on a Constraint Programming solver. Some scheduling problems, known as N P -hard problems, suffer from large computational cost (large number of jobs to schedule) and consequent human effort (well-suited heuristics need to be derived). Moreover industrial scheduling problems obviously evolves over time but a lot of features and the basic structure remain the same. Hence they have potential in the implementation a supervised-learning-based heuristic.

First part of the study was to model a given benchmark of instances and im- plement some famous heuristics (as earliest due date, combined with the largest duration) in order to solve the benchmark.  Based on the none-optimality of returned solutions, primaries instances were choosen to implement our method. The second part represents the procedure which has been set up to design a supervised-learning-based heuristic. An instance generator was first  built to map the potential industrial evolutions of the instances. It returned secondaries instances representing the learning database. Then a CP-well-suited node ex- traction scheme was set up to collect relevant information from the resolution of the search tree. It will  collect data from nodes of the search tree given a proper criteria. These nodes are next projected onto a constant-dimensional space which described the system, the underlying subtree and the impact of the affectations. Upon these features and designed target values statistical mod- els are implemented. A linear and a gradient  boosting regressions have been implemented, calibrated and tuned upon the data. Last was to integrate the supervised-learning model into an heuristic framework. This has been done via a soft propagation module to try  the instantiation of all the children of the considered node and apply the given module upon them. The selection decision rule was based upon a reconstructed score. Third part was to test the procedure implemented. New secondaries instances were generated and supervised- learning-based heuristic tested against the earliest due date one.

The procedure was tested upon two different instances. The integrated heuristic returned positive results for both instances. For the first one (10 jobs to schedule) a gain in the first solution found (resp. the number of backtracks) of 18% (resp. 13% were realized. For the second instance (90 jobs to schedule) a gain in the first solution found of at least 16%. The results come to validate the procedure implemented and the methodology used.

Place, publisher, year, edition, pages
2017.
Series
TRITA-MAT-E, 2017:20
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-207471OAI: oai:DiVA.org:kth-207471DiVA: diva2:1098024
External cooperation
Artelys, France
Subject / course
Optimization and Systems Theory
Educational program
Master of Science in Engineering -Engineering Physics
Supervisors
Examiners
Available from: 2017-05-23 Created: 2017-05-23 Last updated: 2017-05-23Bibliographically approved

Open Access in DiVA

fulltext(4852 kB)29 downloads
File information
File name FULLTEXT01.pdfFile size 4852 kBChecksum SHA-512
4dd07c1760ab6f4c0f8698ba21cf581d51c8b599cd92037200a82db1722b3d56fed37df49ba990e98ef01bf575c3359e50d4cf130defdf261851a9e71e7b1a77
Type fulltextMimetype application/pdf

By organisation
Optimization and Systems Theory
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 29 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 81 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf