Brute, A state-of-the-art inductive program synthesis (IPS) system, introduced a two-phase algorithm; first, complex pro- gram instructions are invented from basic instructions. Sec- ond, a best-first search algorithm finds a sequence of invented instructions to solve an IPS task. This method is limited because invented instructions are always of the same com- plexity, also when less or more complexity is needed. Also, best-first search falls into local optima easily. In this paper, I describe Vlute, an IPS system using Large Neighborhood Search (LNS), in which a solution is gradually improved by exploring neighboring solutions, and Variable-Depth Invent (VDI), in which instruction complexity is increased dynami- cally. Vlute is tested on three IPS domains (robot-planning, string transformations, and drawing ASCII-art). Results show that using VDI improves Vlute’s performance only for string transformation. Vlute can outperform Brute and escape local optima encountered by Brute also only for string transforma- tion. A limitation of Vlute is finding large programs.

Search based synthesis has emerged as a powerful tool in program synthesis, the process of automatically generating implementations for software programs given some form of semantic specification. Search based synthesis involves a search over the space of candidate programs that can be derived from a given grammar. A recently developed new inductive logic programming system called Brute demonstrates how the introduction of example-dependent loss functions can dramatically improve the effectiveness of the search.
However, as problem sizes grow its performance drops and at the same time Brute produces programs that are not optimally concise. To overcome this problem, we develop an alternative to Brute that uses A* search and we make it available in an imperative setting (Python). We study to what extent A* search can aid the synthesis of highly accurate and more concise programs in a shorter amount of time using several bench-marking problems, i.e. string manipulation, robot planning and pixel art. We initially find A* to have a higher accuracy. However, when we introduce the use of a new improved heuristic both methods end up with an equally high performance. These results emphasize the importance of the choice of heuristic and that both methods excel in solving distinct problems and can therefore complement each other.

Inductive Program Synthesis is the problem of generating programs from
a set of input-output examples. Since it can be reduced to the search problem in the space of programs, many search algorithms have been successfully
applied to it over the years. This paper proposes, develops, and analyses
a novel algorithm in the family of Genetic Algorithms, called VanillaGP.
While generally not showing superior performance compared to a recent
best-first Brute method on the subset of program synthesis tasks used in
the paper, VanillaGP does appear to reach a comparable relative improvement of the errors in the training data.

In this research the Metropolis-Hastings algorithmis implemented for the problem of program synthesis and compared with Brute, a best-first search, together with multiple other different search algorithms. The implementation and choices of the Metrolpolis-Hastings algorithm are discussed in detail. The algorithms are tested for three different domains, each with their own associated DSL. Finally, comparisons are drawn between the search algorithms by analyzing the results of these experiments. It is found that the performance of any search algorithm depends very heavily on the specific domain and cost function used and the Metropolis-Hastings algorithm falls short in terms of performance when compared with other conventional methods.

Recently, a new and promising Inductive Program Synthesis (IPS) system, Brute, showed the potential of using a heuristic-based loss function. However, Brute also has its limitations and struggles with escaping local optima. The Monte Carlo Tree Search might offer a solution to this problem since it balances between exploitation and exploration. I design MUTE, a new IPS system which uses MCTS guided by a heuristic-based loss function. MUTE's performance is tested and compared to other IPS systems in three diverse domains, namely robot planning, ASCII art and string transformations. MUTE's performance for string transformations is a first indication that MUTE can outperform Brute and other IPS systems. Manual analysis of the results shows that MUTE can indeed escape local optima. Two branch reducing enhancements, namely the removal of similar programs and the removal of tokens that show no potential, are essential for the success of MUTE.

In this thesis, we have defined a symbolic execution technique to automatically generate test suites for programs written in functional programming languages that can find the behavioural differences between a reference implementation and a set of potentially different implementations. Our symbolic execution technique uses a constraint solver in order to find a model that satisfies all constraints that together represent an execution path through the program. Furthermore, our technique utilises manually defined budget constraints to guide the symbolic execution to more interesting areas of the programs. These budget constraints define an initial budget that dictates when the symbolic execution terminates, and a set of costs associated to certain operations such as calling (specific) functions or performing (specific) pattern matches. This allows the symbolic execution to deplete budgets faster when it explores functions or branches of a program that are deemed "unlikely to be interesting". This results in less system resources being used on exploring these uninteresting execution paths, and instead allows for exploration of deeper paths in more interesting areas of the programs. Our budget constraint optimisation strategy works alongside other well-known optimisation strategies for symbolic execution such as early branch pruning and reusing intermediate results, more commonly known in the field of symbolic execution as compositioning.

In order to perform our symbolic execution on functional programs, we have defined a variation of Control Flow Graphs (CFG) for functional programming languages which allow modelling the execution flow between the different expressions that form the body of functions in functional programming. Additionally, our technique uses a constraint solver in order to find what paths through the program are feasible and to generate inputs that will lead to the execution of said paths. To allow us to specify these constraints on a higher-level, we have defined an intermediate Domain Specific Language (DSL), which can be transformed into a lower-level language understood by the constraint solver. We refer to this DSL as our Intermediate Constraint Language (ICL). Our ICL supports working seamlessly with type systems that allow inheritance, rather than only supporting Algebraic Data Types (ADT).

Furthermore, we have developed a symbolic execution engine for programs written in a pure and functional subset of the Scala programming language. This symbolic execution engine implements our proposed symbolic execution technique alongside the other described optimisation techniques. We have used this implementation in order to measure the effectiveness of our symbolic execution technique. In order to do this, we have used our technique in a scenario to automatically generate test suites for real student submissions of introductory assignments to functional programming. We have performed a comparison between the obtained branch coverages and mutation scores with our technique and the manually written test suites that have been used for multiple years. Finally, we have reflected on the feasibility of using this approach in practice by looking at the execution time and the number of inquiries to the constraint solver, required to generate test suites that are able to find an adequate number of errors.

The increasing global food demand, accompanied by the decreasing number of expert growers, brings the need for more sustainable and efficient solutions in horticulture. Consultancy company Delphy aims to face this challenge by taking a more data-driven approach, by means of autonomous growing inside the greenhouse. The controlled environment of greenhouses enable data collection and precise control. Delphy's current solutions focus on the needs of the crop, but a grower also needs to consider the economic aspect of taking certain decisions on the greenhouse climate. A potential method for solving this complex problem is Constraint Programming (CP). In this work, the applicability of CP for the greenhouse economic optimal control problem will be studied. The contributions of this work are threefold; First, the greenhouse climate is modelled with Long Short-Term Memory (LSTM) and Temporal Convolutional Network (TCN) machine learning models. Secondly, an LSTM model is embedded into a CP model. Lastly, the profit of the grower is optimised through this CP decision support system (DSS). The performed experiments show that both types of time-based machine learning models can model greenhouse temperature and humidity deficit with reasonable accuracy, while light and CO₂ are harder to predict. The correctness of the LSTM-in-CP embedding is validated. The implemented DSS is not yet practically applicable, as the search space is too large to come to reasonable results for realistic instances. For small instances however, the DSS is able to improve the decisions of the grower, demonstrating the potential of using CP for economic greenhouse decision making.

In this paper, we propose a method for eliciting constraints for arbitrary Domain-Specific Languages (DSL) in Program Synthesis search. We argue that we can successfully predict constraints using a form of attribute-based induction. We also provide a novel approach to constraint verification using genetic algorithms to optimize desired results. We implement our approach into GENERALIZE, a novel algorithm for reducing DSL size. GENERALIZE is tested and compared against the default Brute algorithm using 2 different program synthesis domains, robot planning and pixel art. These experiments show that GENERALIZE does not improve performance if good objective functions are available, because of a tendency to get stuck in local heuristic minima. It can increase performance if no such function is available.

In recent months, researchers developed several new search procedures to augment the process of program synthesis. While many of them performed better than their predecessors, the proposed solutions are still far from ideal. One possible way of overcoming the shortcomings of single search methods is employing genetic algorithms, which have been proven useful in many tasks of similar scale. This paper aims to answer the question of whether it is possible to utilize that sort of algorithms to find an efficient combination of search procedures in a program synthesis problem. An implementation of a genetic algorithm is proposed with parameters and operators chosen through a literature study and a series of experiments on three different domains. To outline different approaches to program synthesis, two fitness functions are examined. Finally, evolved search procedures are discussed and compared with the already existing solutions. One of them in particular, namely a combination of Brute and A* algorithms, manages to surpass their singular counterparts in certain cases.

Program synthesis is used in various ways to automate repetitive tasks or to generate software automatically. Search-based program synthesis constitutes searching the space of candidate programs created from a given language. However, this form of program synthesis is very expensive in terms of computing power. By optimising the synthesiser’s parameters on certain tasks, program synthesis can be made more efficient on other similar tasks. One of these parameters is the domain-specific language. Using a genetic algorithm, an optimised language was evolved for three different domains. This resulted in unnecessary language predicates being phased out and commonly used structures being introduced as new language predicates. Overall, using these evolved languages made program synthesis faster for the tasks in all three domains.

Design pattern provide an abstraction that the pro- gram synthesis algorithm can use in order to find programs easier. However, coming up with them is difficult as they are domain-specific. This paper showcases a novel approach to creating design pat- terns through the means of genetic algorithms. Re- sults are showing that while in the robot domain the average time is slightly better, string domain shows that using the patterns actually lowers the accuracy and average time.

Program Synthesis is a challenging problem in Artificial Intelligence. An important element of a program synthesizer is the objective function that guides the combinatorial search for a program that satisfies a given user intent. Given multiple I/O example transformations that correspond to the intended behavior of the program, this function evaluates the performance of a generated program based on the distance of its output to the correct output. In this study, we consider the possibility of using a Genetic algorithm for the evolution of such a function as a means to partially automate the design process. In particular, we propose the GeneticObjective algorithm that evolves domain-specific objective functions by combining user-defined local distance functions in an algebraic expression. Using the Brute synthesizer, we conducted experiments in the Robot Planning and the String transformation domains, the results of which showed that such an approach evolves informative functions. The best evolved function reached the effectiveness of a manually-designed function in the Robot domain, while it outperformed the effectiveness of a hand-crafted function in the String domain.

A recent development in program synthesis is using Monte Carlo Tree Search to traverse the search tree of possible programs in order to efficiently find a program that will successfully transform the given input to the desired output. Previous research has shown promising results as Monte Carlo Tree Search is able to escape local optima that occur during the search. I have continued this previous research by changing some components of Monte
Carlo Tree Search and testing them on three different domains; robot planning, string transformations and ASCII art.
Most notable, I have found that by changing the exploration constant Cp to slowly decrease during the running of the algorithm, you can improve the algorithm’s accuracy. This makes it easier for the algorithm to escape local optima, however here it is crucial the parameters are tuned well. Furthermore, I have also found that improvements can still be made in the expansion step of MCTS. However, changes to which values are backpropagated have not shown an improvement in the accuracy of MCTS in program synthesis.

VanillaGP is an Inductive Program Synthesis algorithm that takes a Genetic Algorithm (GA) approach by using its 3 components: selection, mutation, and crossover. Many different alternatives exist for these components and although this is not the only application of a GAs on the Program Synthesis domain, it has not been extensively evaluated what the effects of using these different alternatives or combinations of them are. We explored this by evaluating the performance of multiple alternatives per component and comparing the results of combinations of these alternatives to VanillaGP. These evaluations were done on 3 IPS domains: robot, ASCII art, and strings. From these evaluations we conclude that Stochastic Universal Sampling combined with Queen Bee Crossover and an altered version of One Mutation Per Solution performs best on the string domain, and Down-Sampled Lexicase Selection combined with Three Parent Crossover and the same altered version of OMPS performs best on the other domains.

Inductive Program Synthesis (IPS) has been implemented by a two-stage search algorithm, Brute, and consequently improved upon with a Large Neighborhood Search (LNS) technique, in an algorithm named Vlute. Unmotivated values and design choices within Vlute caused limitations on the performance of IPS tasks. This research improves upon several of these limitations through experiments. Most significant improvements are found in the robot-planning domain through the implementation of a stochastic accept method and a best improvement neighbor search.

This paper addresses the problem of Inductive Synthesis by analysing the Metropolis-Hastings stochastic search algorithm. The goal of Inductive Synthesis is to generate programs whose intended behaviour is established through the use of input and output examples. The Metropolis-Hastings algorithm searches the set of all possible programs and finds possible solutions. Our experiments show that while optimization can be done under certain conditions, it does not improve the
algorithm’s success rate in synthesizing programs on complex domains compared to more randomized but domainspecific approaches.

The increased heat on an integrated circuit is a limiting factor for the performance and lifetime of a chip. The increased power density on chips resulted in increased heat and the formation of non-uniform hotspots. Earlier research has shown that the package design and layout of package components in flip-chip design can influence the thermal heat distribution on a chip. Especially the copper pillars play a role in the distribution of heat on a chip. These pillars can reduce the maximal temperature of a hotspot when placed correctly. Designing a pillarmap that adheres to manufacturing rules can be lengthy and complex. Therefore, pillarmaps are currently not optimised for thermal behaviour. The default strategy is to place them in a grid. This research aims to automatically optimise pillarmaps for thermal heat distribution with the use of artificial intelligence. Pillarmaps are optimised using the theoretical behaviour of heat in packages combined with Stochastic Hill Climbing and Squeaky Wheel Optimisation techniques. The layouts are automatically re-simulated in a finite elements simulation tool when needed. The optimisation strategies are tested on experimental setups with single and dual hotspots. The optimisation strategies are also evaluated on an actual product, but limitations on pillar placement reduced the effect of the optimisation techniques. Also, the influence of different pillar diameters on an optimisation strategy is discussed. The optimisation techniques can reduce hotspots and improve the heat distribution in a scenario with multiple hotspots. The success of the optimisation techniques is subject to the amount of freedom they have to change pillar locations and where the hotspots are on the chip.