A product-driven system with an evolutionary algorithm to increase flexibility in planning a job shop.

The scheduling of a job shop production system occurs using models to plan operations for a given period while minimizing the makespan. However, since the resulting mathematical models are computationally demanding, their implementation in the work environment is impractical, a difficulty that increases as the scale problem grows. An alternative approach is to address the problem in a decentralized manner, such that real-time product flow information feeds the control system to minimize the makespan dynamically. Under the decentralized approach, we use a holonic and multiagent systems to represent a product-driven job shop system that allows us to simulate real-world scenarios. However, the computational performance of such systems to control the process in real-time and for different problem scales is unclear. This paper presents a product-driven job shop system model that includes an evolutionary algorithm to minimize the makespan. A multiagent system simulates the model and produces comparative results for different problem scales with classical models. One hundred two job shop problem instances classified as small, medium, and large scale are evaluated. The results suggest that a product-driven system produces near-optimal solutions in short periods and improves its performance as the scale of the problem increases. Furthermore, the computational performance observed during the experimentation suggests that such a system can be embedded in a real-time control process.

Best compromise nutritional menus for childhood obesity.

Childhood obesity is an undeniable reality that has rapidly increased in many countries. Obesity at an early age not only increases the risks of chronic diseases but also produces a problem for the whole healthcare system. One way to alleviate this problem is to provide each patient with an appropriate menu that is defined by a mathematical model. Existing mathematical models only partially address the objective and constraints of childhood obesity; therefore, the solutions provided are insufficient for health specialists to prepare nutritional menus for individual patients. This manuscript proposes a multiobjective mathematical programming model to aid in healthy nutritional menu planning that may prevent childhood obesity. This model provides a plan for combinations and amounts of food across different schedules and daily meals. This approach minimizes the major risk factors of childhood obesity (i.e., glycemic load and cholesterol intake). In addition, this approach considers the minimization of nutritional mismatch and total cost. The model is solved using a deterministic method and two metaheuristic methods. Test instances associated with children aged 4-18 years were created with the support of health professionals to complete this numerical study. The quality of the solutions generated using the three methods was similar, but the metaheuristic methods provided solutions in a shorter computational time. These results are submitted to statistical hypothesis tests to be validated. The numerical results indicate proper guidelines for personalized plans for individual children.

Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem.

Genetic algorithms are powerful search methods inspired by Darwinian evolution. To date, they have been applied to the solution of many optimization problems because of the easy use of their properties and their robustness in finding good solutions to difficult problems. The good operation of genetic algorithms is due in part to its two main variation operators, namely, crossover and mutation operators. Typically, in the literature, we find the use of a single crossover and mutation operator. However, there are studies that have shown that using multi-operators produces synergy and that the operators are mutually complementary. Using multi-operators is not a simple task because which operators to use and how to combine them must be determined, which in itself is an optimization problem. In this paper, it is proposed that the task of exploring the different combinations of the crossover and mutation operators can be carried out by evolutionary computing. The crossover and mutation operators used are those typically used for solving the traveling salesman problem. The process of searching for good combinations was effective, yielding appropriate and synergic combinations of the crossover and mutation operators. The numerical results show that the use of the combination of operators obtained by evolutionary computing is better than the use of a single operator and the use of multi-operators combined in the standard way. The results were also better than those of the last operators reported in the literature.

Catechin-based procyanidins from Peumus boldus Mol. aqueous extract inhibit Helicobacter pylori urease and adherence to adenocarcinoma gastric cells.

In this work, the anti-Helicobacter pylori effect of an aqueous extract from dried leaves of Peumus boldus Mol. (Monimiaceae) was evaluated. This extract displayed high inhibitory activity against H. pylori urease. Therefore, in order to clarify the type of substances responsible for such effect, a bioassay-guided fractionation strategy was carried out. The active compounds in the fractions were characterized through different chromatographic methods (RP-HPLC; HILIC-HPLC). The fraction named F5 (mDP = 7.8) from aqueous extract was the most active against H. pylori urease with an IC50 = 15.9 µg gallic acid equivalents (GAE)/mL. HPLC analysis evidenced that F5 was composed mainly by catechin-derived proanthocyanidins (LC-MS and phloroglucinolysis). The anti-adherent effect of boldo was assessed by co-culture of H. pylori and AGS cells. Both the aqueous extract and F5 showed an anti-adherent effect in a concentration-dependent manner. An 89.3% of inhibition was reached at 2.0 mg GAE/mL of boldo extract. In conjunction, our results suggest that boldo extract has a potent anti-urease activity and anti-adherent effect against H. pylori, properties directly linked with the presence of catechin-derived proanthocyanidins.

Automatically generated algorithms for the vertex coloring problem.

The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97% relative error, while four other heuristics selected from the literature present a 59.73% error, considering 29 of the more difficult instances in the DIMACS benchmark.

People efficiently explore the solution space of the computationally intractable traveling salesman problem to find near-optimal tours.

Humans need to solve computationally intractable problems such as visual search, categorization, and simultaneous learning and acting, yet an increasing body of evidence suggests that their solutions to instantiations of these problems are near optimal. Computational complexity advances an explanation to this apparent paradox: (1) only a small portion of instances of such problems are actually hard, and (2) successful heuristics exploit structural properties of the typical instance to selectively improve parts that are likely to be sub-optimal. We hypothesize that these two ideas largely account for the good performance of humans on computationally hard problems. We tested part of this hypothesis by studying the solutions of 28 participants to 28 instances of the Euclidean Traveling Salesman Problem (TSP). Participants were provided feedback on the cost of their solutions and were allowed unlimited solution attempts (trials). We found a significant improvement between the first and last trials and that solutions are significantly different from random tours that follow the convex hull and do not have self-crossings. More importantly, we found that participants modified their current better solutions in such a way that edges belonging to the optimal solution ("good" edges) were significantly more likely to stay than other edges ("bad" edges), a hallmark of structural exploitation. We found, however, that more trials harmed the participants' ability to tell good from bad edges, suggesting that after too many trials the participants "ran out of ideas." In sum, we provide the first demonstration of significant performance improvement on the TSP under repetition and feedback and evidence that human problem-solving may exploit the structure of hard problems paralleling behavior of state-of-the-art heuristics.