Search

Protein structure prediction (PSP) is crucial for biomedical and biological research as it allows accurate prediction of protein structures based ly on their amino acid (AA) sequences. However, this presents a significant challenge in bioinformatics, particularly in drug design. While experimental methods such as X-ray crystallography, Nuclear Magnetic Resonance (NMR), Cryo-electron microscopy (cryo-EM), and Small-angle X-ray scattering (SAXS) can determine protein structures, they are time-consuming, expensive, and often impractical. Recent advancements in machine learning have significantly improved PSP. One significant development is the remarkable success of AlphaFold in the Critical Assessment of Structure Prediction (CASP) competition. However, it is important to acknowledge that most recent methods heavily rely on extensive computational resources and large memory requirements. Interestingly, simpler methods have shown the potential to produce better results. This thesis aims to develop streamlined deep learning methods for PSP, with a specific focus on accurate backbone angle prediction (BAP). As proteins have backbone angles, the folding of proteins is predominantly influenced by backbone angles. Throughout this work, we address various challenges associated with accurate BAP. Our findings illustrate that the implementation of efficient deep learning approaches in PSP significantly enhances the accuracy of predicting protein structures. This thesis focuses on addressing four key challenges associated with protein backbone angles prediction. The first challenge involves exploring feature interactions and neural networks to strike a balance between correlated features and complex neural networks, which is essential for improving accuracy. The thesis introduces the "Simpler Angle Predictor (SAP)" approach, which utilises simplified deep neural network (DNN) models to enhance the accuracy of protein BAP, ensuring interpretability and resilience against noise. T, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Science, Environment, Engineering and Technology, Full Text

Image parsing is fundamental to field of computer vision, and it aids the process of recognising objects and pixels in images. Image parsing refers to assigning pixels in an image to pre-defined object category labels. Traditional machine learning techniques have proven to be inadequate to produce accurate pixel labels and are prone to misclassifications. Therefore, the field of image parsing has gained popularity among researchers and experts in machine learning. As a result, numerous techniques have been proposed. These image parsing techniques, however, have complex architectures and almost lack the consideration of contextual information. There is an enormous body of literature that recognises the importance of image segmentation, presenting an evaluation of it, while the deep learning-based architectures are at the forefront of this developing body of models to perceive images as object labels. The deep learning architectures are mostly based on fully convolutional neural networks and hold the potential to transform the pixel-wise segmentation. Such deep architectures, however, should be developed considering additional context and relevant features. Therefore, the main aim of this thesis is to present novel deep learning-based image parsing architectures that consider contextual information for image parsing and to present component-wise investigations to select the best classifiers, context generations, visual features, and set of hyperparameters used to produce pixel labels. [...], Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Science, Environment, Engineering and Technology, Full Text

Proteins are biomolecules composed of amino acid residues linked together by peptide bonds. A protein’s function depends on its three dimensional native structure, where the native structure has the minimum free energy. Inappropriately folded proteins may cause many severe diseases such as alzheimer, diabetes and cancer. By knowing the structure of a disease protein, it is possible to design a suitable drug molecule to dock on a protein and inhibit its function. Protein structures are very important in drug design. Experimental methods like X-ray crystallography and Nuclear Magnetic Resonance (NMR) spectroscopy that are generally used in determining a protein’s structure are expensive, slow and failure-prone. On the other hand, we only know the native structure of a very few proteins. Computational methods like homology modeling and ab initio modeling have been used to solve the PSP problem. Homology modeling depends on already known similar structure whereas ab initio method that is search based is mostly used when there is very least amount of similarity. Hybrid approaches use both homologs and machine learning to the learnt knowledge, which is exploited during search. The predominant search approaches are local search or population based search. A local search starts with an initial solution. After generating neighbours, it checks the quality of the neighbours. Depending on the quality of the neighbours, it either accepts or rejects the neighbours. Many local search-based approaches have been used for structure prediction. Nevertheless, some challenges still deter the advancement in this field. Such challenges include randomness in neighbour generation, finding out the problematic parts of conformations, handling multiple objectives, handling the complex helix or beta sheets. There are many PSP search algorithms that develop their own proxy energy functions that are known as scoring functions. They use predicted contacts between amino acid residue pairs where two, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Science, Environment, Engineering and Technology, Full Text

Networks are natural but powerful structures that capture relationships between different entities in many domains, such as social networks, citation networks, bioinformatic networks. In many applications that require multiple networks analysis, network alignment, the task of recognizing node correspondence across different networks, plays an important role. A wellknown application of network alignment is to identify which accounts in different social networks belong to the same person. Given the appeal of network alignment, there is a rich body of researches that aims to tackle this problem. However, many research challenges still exist, such as enhancing the accuracy and improving the scalability due to the information explosion. With such motivation, in scope of our PhD work, we address the three crucial challenges in network alignment literature, namely (i) enhancing scalability of network alignment on large-scale graphs, (ii) enhancing the robustness of network alignment to adversarial conditions and (iii) multi-modal information integration for network aligners. To do so, we focus on proposing aligner frameworks for different types of input attributed networks from simple to complex. Each framework attempts to answer simultaneously all three research questions by leveraging embedding techniques, where the input networks are embedded into insightful, low-dimensional vector spaces. This helps to enrich the nodes’ individual context with multi-modal information, thus facilitates the distinction between nodes. The learnt embeddings also enables faster alignment retrieval by direct vector comparison. Our proposed techniques improve upon the state-of-the-art for different types of attributed networks and cover a large range of applications., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Institute of Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

Many real-world problems can be modelled as constraint optimisation problems (COPs). Each COP includes a set of variables with domains of values, constraints on the assignments to the variables, and an objective function, which should be minimised or maximised. In this thesis, we consider only combinatorial COPs, where domains of the variables are discrete. A component is a subproblem of a COP with specific variables, assignable values or constraints. Most practical COPs, including waste collection, mail delivery, supply chain management, and travelling thief problem (TTP), have more than one component. Existing methods for solving COPs, especially multi-component COPs, repeatedly solve the same problem or subproblem but do not take advantage of learning during the search. This research aimed to apply memorising and online or adaptive machine learning models. The memory buffers and the ML models are built, deployed, and updated during the search to improve search efficacy and efficiency in solving COPs, especially multi-component ones. In this research, we have developed a history memorising method to enhance diversity and effectiveness in solving COPs. Also, we have developed three online machine learning-based methods, one coordination learning for improving efficacy and two surrogate models for enhancing the efficiency of TTP solving. Our proposed solver, CoCo, is currently the state-of-the-art solver for solving TTP. History memorising is an online low-level learning method to keep previously visited solutions or their objective values to avoid or escape from local optima during the search. The Late Acceptance Hill Climbing (LAHC) is a history memorising metaheuristic with promising performance on some COP domains. It aims to overcome the main downside of the traditional Hill Climbing (HC) search, which is often quickly trapped in a local optimum due to strictly accepting only non-worsening moves within each iteration. In contrast, LAHC also accepts worsening mo, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Science, Environment, Engineering and Technology, In this thesis, we address the black-box nature of deep learning models for molecular toxicity prediction as well as propose methods for aggregating various chemical features to have an improved accuracy. An ideal toxicity prediction model is characterized with high accuracy, capable of handling descriptors/features diversity, ease of training and interpretability. Considering these attributes of an ideal model, in the first quarter of this thesis we present a novel hybrid framework based on decision trees (DT) and shallow neural networks (SNN). This method paves a path to feature interpretability while enhancing the accuracy by selecting only the relevant features for model training. Using this approach, the run-time complexity of developed toxicity model is substantially reduced. The idea is to create a contextual adaptation of the models by hybridizing the decisions trees to enhance the features interpretability and accuracy both. In the later quarters of this thesis, we argue for the idea of effective aggregation of chemical knowledge about molecules in toxicity prediction. Molecules are represented in various data formats such that each format has its own specific role in predicting molecular activities. We propose various deep learning ensemble approaches to effectively aggregate different chemical features information. We have applied these methods to quantitative and qualitative molecular toxicity prediction problems and have obtained new stateof- the-art accuracy improvements with respect to existing deep learning methods. Our ensembling methods also prove helpful in making the model’s prediction robust over a range of performance metrics for toxicity prediction.

In this thesis, we address the black-box nature of deep learning models for molecular toxicity prediction as well as propose methods for aggregating various chemical features to have an improved accuracy. An ideal toxicity prediction model is characterized with high accuracy, capable of handling descriptors/features diversity, ease of training and interpretability. Considering these attributes of an ideal model, in the first quarter of this thesis we present a novel hybrid framework based on decision trees (DT) and shallow neural networks (SNN). This method paves a path to feature interpretability while enhancing the accuracy by selecting only the relevant features for model training. Using this approach, the run-time complexity of developed toxicity model is substantially reduced. The idea is to create a contextual adaptation of the models by hybridizing the decisions trees to enhance the features interpretability and accuracy both. In the later quarters of this thesis, we argue for the idea of effective aggregation of chemical knowledge about molecules in toxicity prediction. Molecules are represented in various data formats such that each format has its own specific role in predicting molecular activities. We propose various deep learning ensemble approaches to effectively aggregate different chemical features information. We have applied these methods to quantitative and qualitative molecular toxicity prediction problems and have obtained new stateof- the-art accuracy improvements with respect to existing deep learning methods. Our ensembling methods also prove helpful in making the model’s prediction robust over a range of performance metrics for toxicity prediction., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Info & Comm Tech, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Business processes are essential parts of any organisation which define the series of steps performed to achieve their goal. Business processes are normally designed manually by business experts who have deep knowledge of the activities performed in the organi-sations. This knowledge is commonly described in a declarative way as business rules. Organisations have to cope with large numbers of business rules and existing regulations governing the business in which they operate. Such rules are difficult to maintain due to their size and complexity, and it is increasingly challenging to ensure that each business process adheres to those rules. As such, extraction of business processes from rules has three clear advantages: (1) visualisation of all possible executions allowed by the rules,(2) automated execution and compliance by design, (3) identification of “inefficiencies” in the business rules. Extraction of business processes from rules set is a time and re-source consuming process. In this thesis, we have investigated two approaches to extract the business processes from the declarative specification of it. In the first approach, we have investigated the application of constraint satisfaction based planners to automatically extract the business process from the sets of rules specifying it. For this purpose, we have developed a constraint-based automated planner named Transition Constraints for Parallel Planning (TCPP). As a constraint-based planner, it encodes a planning problem as a constraint satisfaction problem and then extracts the plan from the solution to that. TCPP constructs its constraint model from a redefined version of the domain transition graphs (DTG) of a given planning problem. TCPP encodes state transitions in the redefined DTGs by using table constraints with cells containing don’t cares or wild cards. TCPP uses Minion the constraint solver to solve the constraint model and returns a parallel plan. We empirically compare TCPP with the other state-of-the-a

Business processes are essential parts of any organisation which define the series of steps performed to achieve their goal. Business processes are normally designed manually by business experts who have deep knowledge of the activities performed in the organi-sations. This knowledge is commonly described in a declarative way as business rules. Organisations have to cope with large numbers of business rules and existing regulations governing the business in which they operate. Such rules are difficult to maintain due to their size and complexity, and it is increasingly challenging to ensure that each business process adheres to those rules. As such, extraction of business processes from rules has three clear advantages: (1) visualisation of all possible executions allowed by the rules,(2) automated execution and compliance by design, (3) identification of “inefficiencies” in the business rules. Extraction of business processes from rules set is a time and re-source consuming process. In this thesis, we have investigated two approaches to extract the business processes from the declarative specification of it. In the first approach, we have investigated the application of constraint satisfaction based planners to automatically extract the business process from the sets of rules specifying it. For this purpose, we have developed a constraint-based automated planner named Transition Constraints for Parallel Planning (TCPP). As a constraint-based planner, it encodes a planning problem as a constraint satisfaction problem and then extracts the plan from the solution to that. TCPP constructs its constraint model from a redefined version of the domain transition graphs (DTG) of a given planning problem. TCPP encodes state transitions in the redefined DTGs by using table constraints with cells containing don’t cares or wild cards. TCPP uses Minion the constraint solver to solve the constraint model and returns a parallel plan. We empirically compare TCPP with the other state-of-the-a, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Scheduling is a decision-making process, which is employed to allocate resources to tasks in a given time. Scheduling problems are in general NP-hard. In order to solve scheduling problems, three common types of methods have been used: exact methods (e.g., branch & bound and dynamic programming), population based metaheuristics (e.g., genetic algorithm and ant colony optimisation), and local search (LS) algorithms (e.g., simulated annealing and iterated local search). Exact methods are not able to address the practical-sized problems effectively with regard to both CPU times and solution quality. LS algorithms have recently attracted much more attention because of their simplicity, being easy to implement, robustness, and high effectiveness. However, the available LS algorithms in the literature typically use a generic structure for speci fic problems. In other words, the biggest disadvantage of those methods is the lack of problem speci fic components into their algorithmic structures. To ll in this gap, in this thesis, we consider constraint-based local search (CBLS) algorithms to solve scheduling problems because of their effectiveness and also because they are not used much in the scheduling literature. The key difference of CBLS with other LS algorithms is in the use of the problem specifi c information in the search process. CBLS helps the search focus more on areas where efforts will bring more effect, and thus increase the scalability of the search. In other words, CBLS attempts to exploit the essence of the problem and, based on the speci ficities of the problem, defi nes the procedures that will guide the search towards better local optima. The effectiveness of our proposed CBLS techniques is shown throughout this thesis by solving several scheduling problems, such as flowshops with blocking constraints, aircraft operations, and customer order problems. The first scheduling problem is permutation flowshop scheduling problem (PFSP). It is one of the most th

Scheduling is a decision-making process, which is employed to allocate resources to tasks in a given time. Scheduling problems are in general NP-hard. In order to solve scheduling problems, three common types of methods have been used: exact methods (e.g., branch & bound and dynamic programming), population based metaheuristics (e.g., genetic algorithm and ant colony optimisation), and local search (LS) algorithms (e.g., simulated annealing and iterated local search). Exact methods are not able to address the practical-sized problems effectively with regard to both CPU times and solution quality. LS algorithms have recently attracted much more attention because of their simplicity, being easy to implement, robustness, and high effectiveness. However, the available LS algorithms in the literature typically use a generic structure for speci fic problems. In other words, the biggest disadvantage of those methods is the lack of problem speci fic components into their algorithmic structures. To ll in this gap, in this thesis, we consider constraint-based local search (CBLS) algorithms to solve scheduling problems because of their effectiveness and also because they are not used much in the scheduling literature. The key difference of CBLS with other LS algorithms is in the use of the problem specifi c information in the search process. CBLS helps the search focus more on areas where efforts will bring more effect, and thus increase the scalability of the search. In other words, CBLS attempts to exploit the essence of the problem and, based on the speci ficities of the problem, defi nes the procedures that will guide the search towards better local optima. The effectiveness of our proposed CBLS techniques is shown throughout this thesis by solving several scheduling problems, such as flowshops with blocking constraints, aircraft operations, and customer order problems. The first scheduling problem is permutation flowshop scheduling problem (PFSP). It is one of the most th, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, We have designed di erent heuristics for both searching on Massive graphs and regularizing Deep Neural Networks in this work. Both the problem of nding a minimum vertex cover (MinVC) and the maximum edge weight clique (MEWC) in a graph are prominent NP-hard problems of great importance in both theory and application. During recent decades, there has been much interest in nding optimal or near-optimal solutions to these two problems. Many existing heuristic algorithms for MinVC are based on local search strategies. An algorithm called FastVC takes a rst step towards solving the MinVC problem for large real-world graphs. However, FastVC may be trapped at local minima during the local search stage due to the lack of suitable diversi cation mechanisms. Besides, since the traditional best-picking heuristic was believed to be of high complexity, FastVC replaces it with an approximate best-picking strategy. However, best-picking has been proved to be robust for a wide range of problems, so abandoning it may be a great sacri ce. Therefore, we rstly design a diversi cation heuristic to help FastVC escape from local minima, and the proposed solver is named WalkVC. Secondly, we develop a local search MinVC solver, named NoiseVC, which utilizes best-picking (low complexity) with noise to remove vertices during the local search stage in massive graphs. On the other hand, most of existing heuristics for the MEWC problem focus on academic benchmarks with relatively small size. However, very little attention was paid to solving the MEWC problem in large sparse graphs. In this thesis, we exploit the so-called deterministic tournament selection (DTS) heuristic for selecting edges to improve the local search based MEWC algorithms. Deep Neural Networks (DNN), have an extremely large number of parameters comparing with traditional machine earning methods, su er from the the problem of over tting. Dropout [Hinton et al., 2012, Srivastava et al., 2014] has been proposed to address this pr

We have designed di erent heuristics for both searching on Massive graphs and regularizing Deep Neural Networks in this work. Both the problem of nding a minimum vertex cover (MinVC) and the maximum edge weight clique (MEWC) in a graph are prominent NP-hard problems of great importance in both theory and application. During recent decades, there has been much interest in nding optimal or near-optimal solutions to these two problems. Many existing heuristic algorithms for MinVC are based on local search strategies. An algorithm called FastVC takes a rst step towards solving the MinVC problem for large real-world graphs. However, FastVC may be trapped at local minima during the local search stage due to the lack of suitable diversi cation mechanisms. Besides, since the traditional best-picking heuristic was believed to be of high complexity, FastVC replaces it with an approximate best-picking strategy. However, best-picking has been proved to be robust for a wide range of problems, so abandoning it may be a great sacri ce. Therefore, we rstly design a diversi cation heuristic to help FastVC escape from local minima, and the proposed solver is named WalkVC. Secondly, we develop a local search MinVC solver, named NoiseVC, which utilizes best-picking (low complexity) with noise to remove vertices during the local search stage in massive graphs. On the other hand, most of existing heuristics for the MEWC problem focus on academic benchmarks with relatively small size. However, very little attention was paid to solving the MEWC problem in large sparse graphs. In this thesis, we exploit the so-called deterministic tournament selection (DTS) heuristic for selecting edges to improve the local search based MEWC algorithms. Deep Neural Networks (DNN), have an extremely large number of parameters comparing with traditional machine earning methods, su er from the the problem of over tting. Dropout [Hinton et al., 2012, Srivastava et al., 2014] has been proposed to address this pr, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Computing MaximumWeight Cliques (MWC) has many applications in data mining and computer vision including solving graphical models. Among various heuristic methods for MWC, local search is an e ective approach. The local search approach tries to improve the candidate clique by adding, dropping or swapping vertices. It is able to return good solutions in reasonable time periods. In this thesis, we use local search to solve the MWC problem on crafted instances, and then apply the algorithms to solve real-world problems. When we are solving real-world problems, we have to rst model them as an MWC problem and then call an MWC solver. In this modeling process, some domain-speci c knowledge can be much useful in excluding unreasonable solutions or reducing the search space. A considerable proportion of such knowledge can be expressed as a list of mutual exclusion (mutex) constraints, where each mutex constraint indicates that a particular vertex-pair cannot exist in any solution. If we use local search methods, such constraints can reduce the search space and exclude solutions which are unreasonable in real-world. Local search often su ers from the cycling problem, i.e., the search may spend too much time visiting a small area, thus various tabu strategies like con guration checking have been proposed in the literature to deal with this problem. These strategies help improve the intensive search in a promising area. Nevertheless, they may still spend too much time there, so restart is needed to enhance extensive search. Yet current restart strategies are not powerful enough in that they do not restart at a good time point. In this thesis, we propose a cycle estimation-based restart strategy to deal with this problem. It might be the rst time for us to address this fundamental problem of local search. Roughly we use a hash table to detect whether a local optimum is revisited. If so, the search will restart. Also for solving large sparse graphs, we propose e cient data struc

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Combinatorial problems are believed to be hard in general, most of them are at least NPcomplete. Constraint-based approaches employ some convenient and generic techniques to solve these problems. These approaches use basic de nitons to model and wellde ned constraints to represent a problem. Although these approaches produce good results for smaller instances, for large-sized problems these do not perform so well. In this case, problem speci c information can help to increase the scalability of these approaches. Thus in this research, our focus is to nd out theoretically proven and heuristically promising properties that goes beyond the basic de nition of a problem. These properties help to model the problem e ciently and to reduce the e ective search space of a problem. Also, during search these properties can be used as auxiliary or streamlined constraint to boost the e ciency of a search algorithm. These properties along with e cient data structures and modern constraint-based techniques can be used to handle challenging combinatorial problems. The e ectiveness of these techniques is shown throughout this thesis by solving several combinatorial problems, such as optimal Golomb rulers, all-interval series and propositional satis ability. Finding optimal Golomb rulers is an extremely challenging combinatorial problem. Different approaches have been used so far to handle this problem. In this thesis, we provide tight upper bounds for Golomb ruler marks and present symmetry-based domain reduction technique. Using these along with tabu and con guration checking meta-heuristics, we then develop a constraint-based multi-point local search algorithm to perform a satisfaction search for optimal Golomb rulers of speci ed length. We then present an algorithm to perform an optimisation search that minimises the length of a Golomb ruler using the satisfaction search repeatedly. Experimental results demonstrate that our algorithms perform signi cantly better than the existing

Computing MaximumWeight Cliques (MWC) has many applications in data mining and computer vision including solving graphical models. Among various heuristic methods for MWC, local search is an e ective approach. The local search approach tries to improve the candidate clique by adding, dropping or swapping vertices. It is able to return good solutions in reasonable time periods. In this thesis, we use local search to solve the MWC problem on crafted instances, and then apply the algorithms to solve real-world problems. When we are solving real-world problems, we have to rst model them as an MWC problem and then call an MWC solver. In this modeling process, some domain-speci c knowledge can be much useful in excluding unreasonable solutions or reducing the search space. A considerable proportion of such knowledge can be expressed as a list of mutual exclusion (mutex) constraints, where each mutex constraint indicates that a particular vertex-pair cannot exist in any solution. If we use local search methods, such constraints can reduce the search space and exclude solutions which are unreasonable in real-world. Local search often su ers from the cycling problem, i.e., the search may spend too much time visiting a small area, thus various tabu strategies like con guration checking have been proposed in the literature to deal with this problem. These strategies help improve the intensive search in a promising area. Nevertheless, they may still spend too much time there, so restart is needed to enhance extensive search. Yet current restart strategies are not powerful enough in that they do not restart at a good time point. In this thesis, we propose a cycle estimation-based restart strategy to deal with this problem. It might be the rst time for us to address this fundamental problem of local search. Roughly we use a hash table to detect whether a local optimum is revisited. If so, the search will restart. Also for solving large sparse graphs, we propose e cient data struc, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Full Text

Combinatorial problems are believed to be hard in general, most of them are at least NPcomplete. Constraint-based approaches employ some convenient and generic techniques to solve these problems. These approaches use basic de nitons to model and wellde ned constraints to represent a problem. Although these approaches produce good results for smaller instances, for large-sized problems these do not perform so well. In this case, problem speci c information can help to increase the scalability of these approaches. Thus in this research, our focus is to nd out theoretically proven and heuristically promising properties that goes beyond the basic de nition of a problem. These properties help to model the problem e ciently and to reduce the e ective search space of a problem. Also, during search these properties can be used as auxiliary or streamlined constraint to boost the e ciency of a search algorithm. These properties along with e cient data structures and modern constraint-based techniques can be used to handle challenging combinatorial problems. The e ectiveness of these techniques is shown throughout this thesis by solving several combinatorial problems, such as optimal Golomb rulers, all-interval series and propositional satis ability. Finding optimal Golomb rulers is an extremely challenging combinatorial problem. Different approaches have been used so far to handle this problem. In this thesis, we provide tight upper bounds for Golomb ruler marks and present symmetry-based domain reduction technique. Using these along with tabu and con guration checking meta-heuristics, we then develop a constraint-based multi-point local search algorithm to perform a satisfaction search for optimal Golomb rulers of speci ed length. We then present an algorithm to perform an optimisation search that minimises the length of a Golomb ruler using the satisfaction search repeatedly. Experimental results demonstrate that our algorithms perform signi cantly better than the existing, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Inst Integrated&IntelligentSys, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Scheduling problems emerge almost everywhere in real world situations. Efficient scheduling of resources in dynamic complex real world environments continues to pose a significant research challenge. Every real world problem has its own idiosyn- crasies, and environments in the real world are often more complicated. In real world dynamic environments, inevitable and unpredictable real-time events often force a change in scheduled plans. Despite this, most current approaches have been focused on solving simplified scheduling models assuming that all problem characteristics are known in advance. As the hospital’s largest revenue and cost centre, operating rooms are of pivotal importance to hospitals. Any improvement of surgery delivery systems is particularly important for hospitals. With healthcare starting to buckle under the pressures of growing demand and encumbered resources, improving operating room scheduling to deliver a significant improvement in utilisation of this overburdened resource is more important than ever. Motivated with this need, this dissertation describes our efforts to deliver significant improvements to operating room scheduling processes, particularly in Australian public hospitals.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Requirements Engineering (RE) involves processing informal natural language de-scriptions of the system requirements into an integrated and structured formal specification. Current and future software intensive systems must accommodate increasingly larger sets of requirements. Therefore, in large-scale new systems engi- neering projects, the requirements analyst (RA) may end up with many thousands, sometimes tens or even hundreds of thousands, of requirements. Dealing with these large volume of requirements is extremely challenging for several reasons: 1. The system requirements may be unstructured and loosely distributed. 2. They may be ill-defined, incomplete, or redundantly specified. 3. They may change at any time, having ripple effects on others. As a result, the RE process becomes very difficult to manage for a large-scale software intensive system, even if it is somewhat manageable for a small-scale one. In order to streamline the RE process, we present an interactive requirements engineering (iRE) framework. The iRE framework provides automated supports for (1) defects detection and resolution, (2) change management and (3) derivation of integrated and structured system model. Since domain knowledge is necessary in different scenarios, the framework involves the RA in an interactive fashion.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, We are living in a time where a massive 2.5 quintillion bytes of data is generated every day. To realise the value of this data, stream data processing offers a new pro- cessing paradigm that aggregates and analyses large volumes of data quickly. While several commercial Stream Processing Engines (SPEs) are available, it remains dif- ficult to develop stream-based applications. Over the last decade our research has identified and addressed two dominant reasons for this difficulty: Heterogeneity and Stored-Streaming Divide. Heterogeneity highlights the lack of standards in SPEs as well as the wide and changing variety of application requirements. Stored- Streaming Divide is the focus of this thesis. Stored-Streaming Divide emerges from the fact that commercial SPEs treat streaming data and relational data as separate entities even though applications increasingly demand integrated access to both. This integration manifests itself as the join between the stream of fast coming data and relational data sources and is what we call the Stream-Relation Join (SRJ) problem. Two solutions are provided to address the SRJ problem in this thesis. Some commercial SPEs and research projects take a radical approach to ad- dressing the SRJ problem by building an SPE on top of a database from scratch, we call this the stream-relational approach. This approach is cumbersome, it re- quires extensive alteration to the database kernel to process the streaming queries. Alternatively, our approach provides a lean layer that sits between the application and a commercial SPE, which we call the federation layer. This layer extends the database only to the point that it provides just enough functionality to interact with the application and the SPE. In doing so, the federation approach not only efficiently addresses the SRJ problem but ensures the application is portable across a range of commercial SPEs. How to build a federation layer is detailed in this thesis

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, The belief state of a rational agent may be viewed as consisting of sentences that are either beliefs, disbeliefs or neither (non-beliefs). When probabilities are used to model the belief state, beliefs hold a probability of 1, disbeliefs a probability of 0, and non-beliefs a probability between 0 and 1. Probabilistic belief contraction is an operation on the belief state that takes a belief as input and turns it into a non-belief whereas probabilistic belief revision takes a disbelief and turns it into a belief. Given a probabilistic belief state P , the contraction of P by an input a is denoted as Pa− and can be determined as the mixture of P and P ∗a, where P ∗a is the belief state that is a result of revising P by ¬a. The proportion of P and P ∗ that are used in the mixture is set by the mixing factor. Thus, the mixing factor has an important role to play in determining the contracted belief state Pa−.

Scheduling problems emerge almost everywhere in real world situations. Efficient scheduling of resources in dynamic complex real world environments continues to pose a significant research challenge. Every real world problem has its own idiosyn- crasies, and environments in the real world are often more complicated. In real world dynamic environments, inevitable and unpredictable real-time events often force a change in scheduled plans. Despite this, most current approaches have been focused on solving simplified scheduling models assuming that all problem characteristics are known in advance. As the hospital’s largest revenue and cost centre, operating rooms are of pivotal importance to hospitals. Any improvement of surgery delivery systems is particularly important for hospitals. With healthcare starting to buckle under the pressures of growing demand and encumbered resources, improving operating room scheduling to deliver a significant improvement in utilisation of this overburdened resource is more important than ever. Motivated with this need, this dissertation describes our efforts to deliver significant improvements to operating room scheduling processes, particularly in Australian public hospitals., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

Requirements Engineering (RE) involves processing informal natural language de-scriptions of the system requirements into an integrated and structured formal specification. Current and future software intensive systems must accommodate increasingly larger sets of requirements. Therefore, in large-scale new systems engi- neering projects, the requirements analyst (RA) may end up with many thousands, sometimes tens or even hundreds of thousands, of requirements. Dealing with these large volume of requirements is extremely challenging for several reasons: 1. The system requirements may be unstructured and loosely distributed. 2. They may be ill-defined, incomplete, or redundantly specified. 3. They may change at any time, having ripple effects on others. As a result, the RE process becomes very difficult to manage for a large-scale software intensive system, even if it is somewhat manageable for a small-scale one. In order to streamline the RE process, we present an interactive requirements engineering (iRE) framework. The iRE framework provides automated supports for (1) defects detection and resolution, (2) change management and (3) derivation of integrated and structured system model. Since domain knowledge is necessary in different scenarios, the framework involves the RA in an interactive fashion., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

We are living in a time where a massive 2.5 quintillion bytes of data is generated every day. To realise the value of this data, stream data processing offers a new pro- cessing paradigm that aggregates and analyses large volumes of data quickly. While several commercial Stream Processing Engines (SPEs) are available, it remains dif- ficult to develop stream-based applications. Over the last decade our research has identified and addressed two dominant reasons for this difficulty: Heterogeneity and Stored-Streaming Divide. Heterogeneity highlights the lack of standards in SPEs as well as the wide and changing variety of application requirements. Stored- Streaming Divide is the focus of this thesis. Stored-Streaming Divide emerges from the fact that commercial SPEs treat streaming data and relational data as separate entities even though applications increasingly demand integrated access to both. This integration manifests itself as the join between the stream of fast coming data and relational data sources and is what we call the Stream-Relation Join (SRJ) problem. Two solutions are provided to address the SRJ problem in this thesis. Some commercial SPEs and research projects take a radical approach to ad- dressing the SRJ problem by building an SPE on top of a database from scratch, we call this the stream-relational approach. This approach is cumbersome, it re- quires extensive alteration to the database kernel to process the streaming queries. Alternatively, our approach provides a lean layer that sits between the application and a commercial SPE, which we call the federation layer. This layer extends the database only to the point that it provides just enough functionality to interact with the application and the SPE. In doing so, the federation approach not only efficiently addresses the SRJ problem but ensures the application is portable across a range of commercial SPEs. How to build a federation layer is detailed in this thesis, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Full Text

The belief state of a rational agent may be viewed as consisting of sentences that are either beliefs, disbeliefs or neither (non-beliefs). When probabilities are used to model the belief state, beliefs hold a probability of 1, disbeliefs a probability of 0, and non-beliefs a probability between 0 and 1. Probabilistic belief contraction is an operation on the belief state that takes a belief as input and turns it into a non-belief whereas probabilistic belief revision takes a disbelief and turns it into a belief. Given a probabilistic belief state P , the contraction of P by an input a is denoted as Pa− and can be determined as the mixture of P and P ∗a, where P ∗a is the belief state that is a result of revising P by ¬a. The proportion of P and P ∗ that are used in the mixture is set by the mixing factor. Thus, the mixing factor has an important role to play in determining the contracted belief state Pa−., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, The Boolean Satisfiability Problem (SAT) is a prototypical NP-complete problem, and is central in computer science and artificial intelligence. Given a formula over a set of Boolean variables, the SAT problem tests whether an interpretation that satisfies the formula exists. Stochastic Local Search (SLS) is a simple but effective approach to SAT. In this thesis, we proposed new SLS techniques for SAT solving and developed new SLS algorithms. Using empirical evaluations, we showed that at the time they were designed our algorithms performed better than the existing state-of-the-art solvers. Moreover, our algorithms have been established as the latest state-of-the-art algorithms for several types of instances. The first idea is configuration checking (CC) for SAT. A typical CC technique is to forbid flipping a variable if since the last time it was flipped, none of its neighbouring variables has been flipped. Based on this strategy, we developed several solvers, including Swcca and CCAnr. In particular, CCAnr performed very well on crafted instances, and a hybrid solver CCAnr+glucose won the silver prize of Hard-combinatorial track in SAT Competition 2014. The second idea is the notion of multilevel properties which consider the satisfaction degree of clauses. Using the CC strategy and the second level score, we developed the CCASat solver, which won the 2012 SAT Challenge random track. We also proposed several new scoring functions, which were used to design CScoreSAT and HScoreSAT. These two solvers are particularly efficient in solving random SAT instances with long clauses, and show one to two orders of magnitude improvement than previous solvers. Thirdly, we proposed a linear make function for tie-breaking in the famous algorithm WalkSAT, leading to the WalkSATlm algorithm. Our experiments demonstrate that WalkSATlm improves WalkSAT by orders of magnitudes on random k-SAT instances with k > 3.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Business Process Compliance are three words which scholars use to describe what happens, or should happen, when two very di erent worlds collide. The first world is meant to represent enterprises and how they do what they do or, more simply, which procedures and processes they adopt to o er improved products to their customers. Scholars of the field refer to the Business Process Management as a “process optimisation process” and they study approaches, methodologies, and formal languages to describe and improve what they esteem as the heart of every organisation, the business process. A business process can be visualised as a self-contained, temporal, and logical order in which a set of activities ( tasks) are executed to achieve some business objectives. Within a business process, much information is available: The control flow describes what can be done and when, while the relevant data clarify what needs to be work on as well as which actors will do the work. The second world is the world of governments, of consortia, of all those entities which have enough power to create regulations, norms, and policies which directly impact organisations. Such entities state the boundaries of legality by imposing which actions can be considered legal to be performed within the aforementioned business processes, and which actions should be avoided in order not to incur severe sanctions.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Proteins are considered to be one of the most important biological macromolecules and play a wide range of vital roles in most biological interactions. Therefore, determining how they function is an important task in biology and biomedical science. Protein fold recognition is defined as assigning a given protein to a fold (among a finite number of folds) that represents its functionality as well as its major tertiary structure. Despite all the efforts made over the last two decades, finding an effective computational approach to solve this problem still remains challenging for computational biology and bioinformatics. In this study we enhance the protein fold prediction accuracy by employing evolutionary and structural information for feature extraction. Based on our previously proposed feature extraction techniques to extract physicochemical-based features, we develop segmented distribution and segmented auto-covariance feature extraction methods to extract local evolutionary and structural information. By applying an SVM to our extracted features, we enhance the protein fold prediction accuracy up to 7.2% better than the best result found in the literature. In conclusion, we develop several segmentation-based feature extraction techniques that enable us to extract local discriminatory information for protein fold recognition better than previously proposed approaches to achieve this goal.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Proteins form a group of one of the most vital macromolecules in living organisms. Yet, even a single mutation in a protein sequence may result in significant changes in protein stability, structure, and thus in protein function as well. Therefore, reliable prediction of stability changes induced by protein mutations is an important aspect of computational protein design, which can aid novel medical and technological discoveries. Also, many mutations have a functional impact which may lead to a disease. Therefore, a key component of personalised medicine is to fully annotate human genetic variations among different individuals. Obviously, it would be infeasible to examine the impact of each possible variant experimentally. Instead, computational methods are needed for a quick and large-scale annotation of genetic variants. In this thesis, we proposed machine learning methods for predicting stability changes induced by single amino acid substitutions and for detecting disease-causing frameshifting indels (genetic variants caused by short insertions and deletions in the DNA sequence) and nonsense mutations (single nucleotide variants which truncate the protein sequence). The proposed methods can predict the effects of these mutations without the knowledge of the protein structure, which make them applicable universally to all proteins encoded in the human genome.

Business Process Compliance are three words which scholars use to describe what happens, or should happen, when two very di erent worlds collide. The first world is meant to represent enterprises and how they do what they do or, more simply, which procedures and processes they adopt to o er improved products to their customers. Scholars of the field refer to the Business Process Management as a “process optimisation process” and they study approaches, methodologies, and formal languages to describe and improve what they esteem as the heart of every organisation, the business process. A business process can be visualised as a self-contained, temporal, and logical order in which a set of activities ( tasks) are executed to achieve some business objectives. Within a business process, much information is available: The control flow describes what can be done and when, while the relevant data clarify what needs to be work on as well as which actors will do the work. The second world is the world of governments, of consortia, of all those entities which have enough power to create regulations, norms, and policies which directly impact organisations. Such entities state the boundaries of legality by imposing which actions can be considered legal to be performed within the aforementioned business processes, and which actions should be avoided in order not to incur severe sanctions., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

The Boolean Satisfiability Problem (SAT) is a prototypical NP-complete problem, and is central in computer science and artificial intelligence. Given a formula over a set of Boolean variables, the SAT problem tests whether an interpretation that satisfies the formula exists. Stochastic Local Search (SLS) is a simple but effective approach to SAT. In this thesis, we proposed new SLS techniques for SAT solving and developed new SLS algorithms. Using empirical evaluations, we showed that at the time they were designed our algorithms performed better than the existing state-of-the-art solvers. Moreover, our algorithms have been established as the latest state-of-the-art algorithms for several types of instances. The first idea is configuration checking (CC) for SAT. A typical CC technique is to forbid flipping a variable if since the last time it was flipped, none of its neighbouring variables has been flipped. Based on this strategy, we developed several solvers, including Swcca and CCAnr. In particular, CCAnr performed very well on crafted instances, and a hybrid solver CCAnr+glucose won the silver prize of Hard-combinatorial track in SAT Competition 2014. The second idea is the notion of multilevel properties which consider the satisfaction degree of clauses. Using the CC strategy and the second level score, we developed the CCASat solver, which won the 2012 SAT Challenge random track. We also proposed several new scoring functions, which were used to design CScoreSAT and HScoreSAT. These two solvers are particularly efficient in solving random SAT instances with long clauses, and show one to two orders of magnitude improvement than previous solvers. Thirdly, we proposed a linear make function for tie-breaking in the famous algorithm WalkSAT, leading to the WalkSATlm algorithm. Our experiments demonstrate that WalkSATlm improves WalkSAT by orders of magnitudes on random k-SAT instances with k > 3., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

Proteins form a group of one of the most vital macromolecules in living organisms. Yet, even a single mutation in a protein sequence may result in significant changes in protein stability, structure, and thus in protein function as well. Therefore, reliable prediction of stability changes induced by protein mutations is an important aspect of computational protein design, which can aid novel medical and technological discoveries. Also, many mutations have a functional impact which may lead to a disease. Therefore, a key component of personalised medicine is to fully annotate human genetic variations among different individuals. Obviously, it would be infeasible to examine the impact of each possible variant experimentally. Instead, computational methods are needed for a quick and large-scale annotation of genetic variants. In this thesis, we proposed machine learning methods for predicting stability changes induced by single amino acid substitutions and for detecting disease-causing frameshifting indels (genetic variants caused by short insertions and deletions in the DNA sequence) and nonsense mutations (single nucleotide variants which truncate the protein sequence). The proposed methods can predict the effects of these mutations without the knowledge of the protein structure, which make them applicable universally to all proteins encoded in the human genome., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Full Text

Proteins are considered to be one of the most important biological macromolecules and play a wide range of vital roles in most biological interactions. Therefore, determining how they function is an important task in biology and biomedical science. Protein fold recognition is defined as assigning a given protein to a fold (among a finite number of folds) that represents its functionality as well as its major tertiary structure. Despite all the efforts made over the last two decades, finding an effective computational approach to solve this problem still remains challenging for computational biology and bioinformatics. In this study we enhance the protein fold prediction accuracy by employing evolutionary and structural information for feature extraction. Based on our previously proposed feature extraction techniques to extract physicochemical-based features, we develop segmented distribution and segmented auto-covariance feature extraction methods to extract local evolutionary and structural information. By applying an SVM to our extracted features, we enhance the protein fold prediction accuracy up to 7.2% better than the best result found in the literature. In conclusion, we develop several segmentation-based feature extraction techniques that enable us to extract local discriminatory information for protein fold recognition better than previously proposed approaches to achieve this goal., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Proteins that are essentially sequences of amino acids, adopt specific folded 3-dimensional (3D) structures to perform their specific tasks. However, misfolded proteins cause fatal diseases. Hence, protein structure prediction (PSP) has emerged as an important multi-disciplinary research problem. Given a protein sequence, the PSP problem is to find a 3D structure of the protein such that the total free energy amongst the amino acids in the sequence is minimised. In-vitro laboratory methods are time-consuming, expensive, and failure-prone. Conversely, computational methods are NP-hard even when the models are simplified by using low-resolution energy functions and lattice-based structures.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, This thesis presents our research on protein structure prediction on discrete lattices. Given a protein’s amino acid sequence, the protein structure prediction problem is to find its three dimensional native structure that has the minimum free energy. Knowledge about the native protein structures and their respective folding process is a key to understand protein functionalities and consequently the basics of life. Protein structure prediction problem is one of the most challenging problems in molecular biology. In-vitro laboratory methods applied to this problem are very time-consuming, cost- expensive and failure-prone. Also, the search based optimization methods used are com- putationally very expensive. To tackle these, researchers have used various simplified models, such as low resolution energy functions and lattice-based structures, and applied incomplete local search methods on them. The simplified models help obtain back-bone structures first and then hierarchically work out the details. Local search methods can normally quickly find solutions although they suffer from re-visitation and stagnancy, and require good heuristics. In the literature, researchers have mostly used primitive ap- proaches based on random decisions at various choice points. Consequently, these methods are applicable to small-sized proteins only. In this thesis, we present a number of techniques to improve the performance of lo- cal search methods applied to protein structure prediction problem using discrete lattices. Firstly, we propose a memory based local search framework that maintains a set of already explored solutions for avoiding re-visitation and stores previously unexplored but promi- nent solutions for restarting to handle stagnation. A novel encoding scheme for protein structures is proposed to handle symmetry present in the search space. We also propose an approximate matching strategy that results in reducing redundancy in the search space.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, In recent years, the Propositional Satisfiability (SAT) has become standard for encoding real world complex constrained problems. SAT has significant impacts on various research fields in Artificial Intelligence (AI) and Constraint Programming (CP). SAT algorithms have also been successfully used in solving many practical and industrial applications that include electronic design automation, default reasoning, diagnosis, planning, scheduling, image interpretation, circuit design, and hardware and software verification. The most common representation of a SAT formula is the Conjunctive Normal Form (CNF). A CNF formula is a conjunction of clauses where each clause is a disjunction of Boolean literals. A SAT formula is satisfiable if there is a truth assignment for each variable such that all clauses in the formula are satisfied. Solving a SAT problem is to determine a truth assignment that satisfies a CNF formula. SAT is the first problem proved to be NP-complete [20]. There are many algorithmic methodologies to solve SAT. The most obvious one is systematic search; however another popular and successful approach is stochastic local search (SLS). Systematic search is usually referred to as complete search or backtrack-style search. In contrast, SLS is a method to explore the search space by randomisation and perturbation operations. Although SLS is an incomplete search method, it is able to find the solutions effectively by using limited time and resources. Moreover, some SLS solvers can solve hard SAT problems in a few minutes while these problems could be beyond the capacity of systematic search solvers.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Business Process Management approach allows an organisation to control every aspect of its internal processes (also called business processes) to im- prove them continuously, and to achieve at the same time the organisational objectives (or goals) business processes are built for. When the enterprise is seen as an entity embedded in an environment regulated by norms, the concept of norm compliance comes into play. Norm compliance is the alignment of the formal specifications of a (set of) business process(es), and the formal specifications of the set of norms governing the surrounding environment. While this topic gave rise through the years to an entire re- search field (Business Process Compliance), to the best of our knowledge little attention has been given on how enterprises should behave in case of normative changes, or what are the actual implications on regulatory compliance in case of deliberatory process changes. In this situation, or- ganisations have to face important questions. Are business processes still compliant with the normative? And if not, is it possible to recover compli- ance? How to revise business processes and adjust their behaviour with respect to these changes?

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, A mobile ad-hoc network(MANET) is a collection of wireless mobile nodes. These nodes are self-organized to create a temporally connection between them without any pre-defined network infrastructure. Nodes communicate each other via direct shared wireless radio links. Each mobile node has limited transmission range. Co- operative nodes, willing to communicate with other nodes out of their transmission range, employ a multi-hop strategy. Therefore, each node simultaneously acts as a router and as a host. Nodes can also join and leave the network at any time. These nodes usually have limited battery life. Nodes are capable of saving their battery power by switching off. They can be switched on when they need to communicate again. Due to their dynamic topology, MANETs are very useful. However this dynamic nature can cause nodes to be compromised easily. Therefore, in this setting, trust is considered to be a key concept in securing MANET environment. But the notion of trust is not granted, as it is measured by observation with time. Besides, mobility of nodes between clusters of MANETs, poses a significant challenge to recommender systems. The ‘new-node‘ problem is difficult to tackle, since without previous preferences of a node, it is not possible to find similar ratings to build a recommender-based profile. Therefore this research presents a rationale and design for much richer dynamic trust management than it is possible today.

This thesis presents our research on protein structure prediction on discrete lattices. Given a protein’s amino acid sequence, the protein structure prediction problem is to find its three dimensional native structure that has the minimum free energy. Knowledge about the native protein structures and their respective folding process is a key to understand protein functionalities and consequently the basics of life. Protein structure prediction problem is one of the most challenging problems in molecular biology. In-vitro laboratory methods applied to this problem are very time-consuming, cost- expensive and failure-prone. Also, the search based optimization methods used are com- putationally very expensive. To tackle these, researchers have used various simplified models, such as low resolution energy functions and lattice-based structures, and applied incomplete local search methods on them. The simplified models help obtain back-bone structures first and then hierarchically work out the details. Local search methods can normally quickly find solutions although they suffer from re-visitation and stagnancy, and require good heuristics. In the literature, researchers have mostly used primitive ap- proaches based on random decisions at various choice points. Consequently, these methods are applicable to small-sized proteins only. In this thesis, we present a number of techniques to improve the performance of lo- cal search methods applied to protein structure prediction problem using discrete lattices. Firstly, we propose a memory based local search framework that maintains a set of already explored solutions for avoiding re-visitation and stores previously unexplored but promi- nent solutions for restarting to handle stagnation. A novel encoding scheme for protein structures is proposed to handle symmetry present in the search space. We also propose an approximate matching strategy that results in reducing redundancy in the search space., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

In recent years, the Propositional Satisfiability (SAT) has become standard for encoding real world complex constrained problems. SAT has significant impacts on various research fields in Artificial Intelligence (AI) and Constraint Programming (CP). SAT algorithms have also been successfully used in solving many practical and industrial applications that include electronic design automation, default reasoning, diagnosis, planning, scheduling, image interpretation, circuit design, and hardware and software verification. The most common representation of a SAT formula is the Conjunctive Normal Form (CNF). A CNF formula is a conjunction of clauses where each clause is a disjunction of Boolean literals. A SAT formula is satisfiable if there is a truth assignment for each variable such that all clauses in the formula are satisfied. Solving a SAT problem is to determine a truth assignment that satisfies a CNF formula. SAT is the first problem proved to be NP-complete [20]. There are many algorithmic methodologies to solve SAT. The most obvious one is systematic search; however another popular and successful approach is stochastic local search (SLS). Systematic search is usually referred to as complete search or backtrack-style search. In contrast, SLS is a method to explore the search space by randomisation and perturbation operations. Although SLS is an incomplete search method, it is able to find the solutions effectively by using limited time and resources. Moreover, some SLS solvers can solve hard SAT problems in a few minutes while these problems could be beyond the capacity of systematic search solvers., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Full Text

Proteins that are essentially sequences of amino acids, adopt specific folded 3-dimensional (3D) structures to perform their specific tasks. However, misfolded proteins cause fatal diseases. Hence, protein structure prediction (PSP) has emerged as an important multi-disciplinary research problem. Given a protein sequence, the PSP problem is to find a 3D structure of the protein such that the total free energy amongst the amino acids in the sequence is minimised. In-vitro laboratory methods are time-consuming, expensive, and failure-prone. Conversely, computational methods are NP-hard even when the models are simplified by using low-resolution energy functions and lattice-based structures., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

Business Process Management approach allows an organisation to control every aspect of its internal processes (also called business processes) to im- prove them continuously, and to achieve at the same time the organisational objectives (or goals) business processes are built for. When the enterprise is seen as an entity embedded in an environment regulated by norms, the concept of norm compliance comes into play. Norm compliance is the alignment of the formal specifications of a (set of) business process(es), and the formal specifications of the set of norms governing the surrounding environment. While this topic gave rise through the years to an entire re- search field (Business Process Compliance), to the best of our knowledge little attention has been given on how enterprises should behave in case of normative changes, or what are the actual implications on regulatory compliance in case of deliberatory process changes. In this situation, or- ganisations have to face important questions. Are business processes still compliant with the normative? And if not, is it possible to recover compli- ance? How to revise business processes and adjust their behaviour with respect to these changes?, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Full Text

A mobile ad-hoc network(MANET) is a collection of wireless mobile nodes. These nodes are self-organized to create a temporally connection between them without any pre-defined network infrastructure. Nodes communicate each other via direct shared wireless radio links. Each mobile node has limited transmission range. Co- operative nodes, willing to communicate with other nodes out of their transmission range, employ a multi-hop strategy. Therefore, each node simultaneously acts as a router and as a host. Nodes can also join and leave the network at any time. These nodes usually have limited battery life. Nodes are capable of saving their battery power by switching off. They can be switched on when they need to communicate again. Due to their dynamic topology, MANETs are very useful. However this dynamic nature can cause nodes to be compromised easily. Therefore, in this setting, trust is considered to be a key concept in securing MANET environment. But the notion of trust is not granted, as it is measured by observation with time. Besides, mobility of nodes between clusters of MANETs, poses a significant challenge to recommender systems. The ‘new-node‘ problem is difficult to tackle, since without previous preferences of a node, it is not possible to find similar ratings to build a recommender-based profile. Therefore this research presents a rationale and design for much richer dynamic trust management than it is possible today., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, A protein is formed by a string of amino acids folding into a specic three-dimensional shape. Experimental approaches used to determine a protein's three-dimensional structure are time consuming and resource demanding. Therefore, computational methods that predict protein structure have been introduced. Computational protein structure predition (PSP) methods can be grouped into three main categories: comparative modelling, threading, and ab initio. Ab initio methods try to predict a protein's three-dimensional structure from its sequence alone. This is based on `Ansen's Thermodynamic Hypothesis' that a protein's native conformation is at its free-energy minimum. However, the biggest problem that the ab initio eld faces is that the free-energy landscape is very irregular and high-dimensional. To minimise this problem the concept of fragments was introduced to limit the number of conformations considered for a particular segment of the protein chain. Fragments can be applied to most PSP search techniques. A promising search method in PSP is the Genetic Algorithm (GA), as they allow for a generic search strategy. GAs provide a way of recombining good genetic traits from generation to generation, which allows them to easily be applied to feature-based resampling. Feature-based resampling focuses on taking an already sampled search space and recombining features from it, in order to improve the nal solution. In the literature feature-based resampling using GAs has been mentioned, primarily concerning the use of strings of torsion angles, and low-resolution PSP models to represent the protein structure. The biggest problem that can be seen from this is that torsion angles are unable to capture larger-scale elements of protein structure.

A protein is formed by a string of amino acids folding into a specic three-dimensional shape. Experimental approaches used to determine a protein's three-dimensional structure are time consuming and resource demanding. Therefore, computational methods that predict protein structure have been introduced. Computational protein structure predition (PSP) methods can be grouped into three main categories: comparative modelling, threading, and ab initio. Ab initio methods try to predict a protein's three-dimensional structure from its sequence alone. This is based on `Ansen's Thermodynamic Hypothesis' that a protein's native conformation is at its free-energy minimum. However, the biggest problem that the ab initio eld faces is that the free-energy landscape is very irregular and high-dimensional. To minimise this problem the concept of fragments was introduced to limit the number of conformations considered for a particular segment of the protein chain. Fragments can be applied to most PSP search techniques. A promising search method in PSP is the Genetic Algorithm (GA), as they allow for a generic search strategy. GAs provide a way of recombining good genetic traits from generation to generation, which allows them to easily be applied to feature-based resampling. Feature-based resampling focuses on taking an already sampled search space and recombining features from it, in order to improve the nal solution. In the literature feature-based resampling using GAs has been mentioned, primarily concerning the use of strings of torsion angles, and low-resolution PSP models to represent the protein structure. The biggest problem that can be seen from this is that torsion angles are unable to capture larger-scale elements of protein structure., Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Full Text

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Radio Frequency Identication (RFID) technology refers to the use of tags with unique identiers being attached to various items which are scanned without a line of sight and then recorded into a database. Current integrations of this technology include baggage tracking at airports, pet owner identication and tagging objects in stores to enforce security by alerting management when an item has left the facility without the tag being deactivated. Despite the wide-scale adoption and advantages of RFID, several issues exist that introduce a level of unreliability resulting in the technology only being used in a fraction of its potential applications. Persistent anomalies that exist in the captured data sets can be classied into either false-positive or false-negative readings. Several methodologies have been presented in the past to correct RFID anomalies, however, due to a lack of intelligence or necessary information, the maximum integrity is not always possible to achieve by currently used techniques. To enhance the overall accuracy of RFID systems, this research proposes a means to correct stored RFID data based on both intelligent analysis and classiers employed at a deferred stage of the data capturing process. We have investigated three classiers due to their impressive performance and novelty to conduct our investigation: a Bayesian Network, Neural Network and Non-Monotonic Reasoning. The main contribution of this thesis involves applying the Bayesian Network [Darcy et al., 2009b], Neural Network [Darcy et al., 2010b] and Non-Monotonic Reasoning [Darcy et al., 2009a, Darcy et al., 2010c] classiers to clean both false-negative and false-positive [Darcy et al., 2011c, Darcy et al., 2012a] anomalies. From our ndings [Darcy et al., 2011a], our proposed methodologies have improved the cleaning accuracy of existing state-of-the-art techniques and have been found to be statistically signicant [Darcy et al., 2007, Darcy et al., 2009c]. We have also proposed further exten

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, It is essential to ensure the correctness of software systems, especially for large and safety-critical pplications. Detecting problems earlier in the software cycle, such as in the specification and design phases, would significantly reduce the costs involved. Rigorous automated approaches are ideal for detecting such problems. Model checking is an automated verification technique which exhaustively searches the state space to determine whether a model of the system satisfies a given property. However, model checking suffers from state explosion, preventing large systems from being verified. The Behavior Tree specification language enables engineers to handle the complexity of large systems, by allowing them to focus on one requirement at a time. Behavior Trees maintain strong links to the original requirements of the system. There has been support for automatic translation of Behavior Trees into model checking languages. However, due to the state explosion problem, large Behavior Trees still cannot be verified. Program slicing is a reduction technique which automatically removes irrelevant portions of the program, usually applied for improving understanding and debugging. In this thesis, a technique for reducing Behavior Trees prior to verification is proposed, based on the concepts of program slicing. The technique is shown to preserve all properties specified in the language CTL* -X, which is CTL* without the next operator. Thus, a property will be proved on the sliced model if and only if it is proved on the original model. The slicing approach is demonstrated on two case studies, producing significant reductions in verification time.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), Institute for Integrated and Intelligent Systems, Science, Environment, Engineering and Technology, Maintaining control over the autonomous agents is a major concern in MultiAgent Systems (MAS). Social laws or norms are used to specify the expected ideal behaviors from the agents. Although several norm enforcement mechanisms are developed to encourage the agents to remain compliant with the norms or the social laws, still there is a lack of a formal analysis of punishment in MAS. In this thesis, we develop punishment models and analyze certain implementation issues. Our contributions are twofold, firstly, we model the punishment procedure and then, we study certain side effects of executing the punishment. We model a MAS as a network and punishment as cuts in that network. A cut separates the violators from the compliant agents. As they can not interact with the compliant agents, they are deprived from the utility that they would get from executing certain joint actions with the compliant agents. Hence they get punished. This form of punishment is common in our society such as `jail' or `economic sanctions'. In this context, we use auctions, coalitional games and party affiliation game to analyze the punishment procedure. Based on these models of punishment we develop a punishment regimentation mechanism, that compels the compliant agents to punish the violators. Additionally, we use NAE-SAT games to analyze the adverse eects of such regimentation. In the second part of the thesis, we study the side effects of isolating the violators, which can decrease the connectivity of the MAS. As connectivity is decreased, agents are less likely to collaborate. Hence the efficiency of the MAS also decreases. We use edge augmentation to recover connectivity. In this context, we study Nash equilibrium of an edge augmentation game and nally, we use multiple source spanning tree completion problems to study more complex scenarios of connectivity recovery.

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, The hyperlinked part of the internet known as "the Web" arose without much planning for a future of millions of publishers and countless pieces of online content. It has no in-built mechanism to find anything, so tools external to it were introduced: initially web directories and then search engines. Search engines are based on machine learning and have been extremely successful. However, they have some inherent limitations and cannot, by design, address some needs: they serve the "information locating" need only and not "information discovery". Search engine users have learned to accept them and in many cases do not realise how their search has been limited by shortcomings of the model. Before the advent of the search engine, web directories were the only information-finding tool on the web. They were manually built and could not compete economically with the effciency of search engines. This lead to their virtual extinction, with the effect that the "information discovery" need of users is no longer served by any major information provider. Furthermore, none of the dominant information-finding models account for the person of the user in any meaningful way controllable by (or even visible to) the user. This work proposes a method to combine a search engine, a web directory and a personal information management agent into an intelligent Web Exploration Engine in a way which bridges the gaps between these seemingly unrelated tools. Our hybrid, for which we have developed a proof-of-concept prototype [Kalinov et al., 2010b], allows users to both locate specific data and to discover new information. Information discovery is served by a web directory which is built with the assistance of a dynamic hierarchical classifier we developed [Kalinov et al., 2010a]. The category structure achieved by it is also the basis of a large number of nested search engines, allowing information locating both in general (similar to a "standard" search engine) and in a variety of contexts

Full Text, Thesis (PhD Doctorate), Doctor of Philosophy (PhD), School of Information and Communication Technology, Science, Environment, Engineering and Technology, Since 1992 a popular and appealing technique for solving planning problems has been to use a general purpose solution procedure for Boolean SAT(isfiability) problems. In this setting, a fixed horizon instance of the problem is encoded as a formula in propositional logic. A SAT procedure then computes a satisfying valuation for that formula, or otherwise proves it unsatisfiable. Here, the SAT encoding is constructive in the usual sense that there is a one-to-one correspondence between plans –i.e., solutions to the planning problem– and satisfying valuations of the formula. One of the biggest drawbacks of this approach is the enormous sized formulae generated by the proposed encodings. In this thesis we mitigate that problem by developing, implementing, and evaluating a novel encoding that uses the techniques of splitting and factoring to develop a compact encoding that is amenable to state-of-the-art SAT procedures. Overall, our approach is the most scalable, and our representation the most compact amongst optimal planning procedures. We then examine planning with numeric quantities, and in particular optimal planning with action costs. SAT-based procedures have previously been proposed in this setting for the fixed horizon case, where there is a given limit on plan length, however a key challenge has been to develop a SAT-based procedure that can achieve horizon-independent optimal solutions – i.e., the least costly plan irrespective of length. Meeting that challenge, in this thesis we develop a novel horizon-independent optimal procedure that poses partially weighted MaxSAT problems to our own cost-optimising conflict-driven clause learning (CDCL) procedure. We perform a detailed empirical evaluation of our approach, detailing the types of problem structures where it dominates. Finally, we take the insights gleaned for the classical propositional planning case, and develop a number of encodings of problems that are described using control-knowledge. That control kn