Hierarchical optimization of personalized experiences for e-Learning systems through evolutionary models

Abstract

Recent researches in e-Learning area highlight the need to define novel and advanced support mechanism for commercial and academic organizations in order to enhance the skills of employees and students and, consequently, to increase the overall competitiveness in the new economy world. This is due to the unbelievable velocity and volatility of modern knowledge that require novel learning methods which are able to offer additional support features as efficiency, task relevance and personalization. This paper tries to deal with these features by proposing an adaptive e-Learning framework based on Computational Intelligence methodologies by supporting e-Learning systems’ designers in two different aspects: (1) they represent the most suitable solution, able to support learning content and activities, personalized to specific needs and influenced by specific preferences of the learner and (2) they assist designers with computationally efficient methods to develop “in time” e-Learning environments. Our work attempts to achieve both results by exploiting an ontological representation of learning environment and a hierarchical memetic approach of optimization. In detail, our approach takes advantage of a collection of ontological models and processes for adapting an e-Learning system to the learner expectations by efficiently solving a well-defined optimization problem, through a hierarchical multi-cores memetic approach.

1 Introduction

The dominant approach in technology enhanced learning has been, for many years, the information transfer, which is based upon the central figure of the teacher whose primary activity is the provisioning of educational contents to be transferred to learners that consume these contents in a passive way. As a consequence, many e-Learning solutions provide a simple “digitalization of this approach and, in most cases, they are remote learning software platforms, where focus is on the educational resources, that is only an input of the whole learning process, and on their presentation (delivery). This aspect, together with other relevant omissions, like the support for pedagogies, the contextualization of the learning experience and the engagement of the learner in activities, are considered the main barriers to e-Learning adoption and trace the way where looking forward for future developments. In particular, the existing e-Learning solutions, demanding everything to the content:

• 1. superimpose to learners how they have to learn without taking into account learners dispositions or preferences, and

• 2. constrain learners to learn and teachers to teach following a predefined approach. Entering the so-called knowledge society, e-Learning solutions must second a real evolution where the main efforts should be devoted to support the whole learning process, not only specific parts of the process (i.e. content management, resource delivery, etc.).

In order to overcome the well-recognized limitations of the learning paradigm supported by the current commercial Learning Management Systems (LMS) [1] and to support the new e-Learning trends, we need suitable models and processes that dynamically and intelligently create e-Learning experiences (i.e. a structured collection of content and services able to facilitate learners in acquiring a set of competencies about a specific domain) adapted to learner expectations and objectives in the new Web environment.

In this paper, we introduce an approach for defining personalized e-Learning experiences (intended as most fitting sequences of learning activities able to maximize the understanding level of learners with respect to specific learning objectives) exploiting machine-understandable representations of educational domains and learners characteristics integrated together in a computational intelligence framework. These aims have been achieved through the joint use of different methodologies and techniques:

• ontological methodologies [2], able to model and represent the educational domains of interest realizing a conceptualization of an educational domain by identifying its relevant subjects and organizing them by means of a fixed set of relations [3],

• user modeling techniques [4], able to represent in a convenient way the learning preferences and the cognitive states of learners involved in the process

• graph algorithms [5], used to navigate educational ontologies and perform reasoning on them in order to derive personalized learning paths, i.e. personalized sequences of subjects to be learnt in order to reach specific learning objectives.

While the three aforementioned aspects are already settled, in order to complete the personalized e-Learning experience building process, we lack of a convenient way to bind subjects, included in personalized learning paths, with learning activities (realized with learning services and learning objects) selected on the base of learner preferences. A given learning activity will offer to the learner an environment able to support the learning of one or more specific subjects in his/her personalized learning path.

A possible approach to face the binding problem is to consider it as a Plant Location Problem (PLP) [6] and solve it with a specific deterministic algorithm. This approach is convenient when we are considering a repository with a limited number of learning activities and learning paths with few subjects. But when the execution environment is the Web 2.0 with distributed repositories and the learning paths are made by numerous subjects, we need to investigate other solutions. Indeed, since the PLP is an NP-hard problem should be more convenient to exploit an approximate method of resolution based on evolutionary computation methodologies; in this way, we are sure that the proposed e-Learning system is capable of generating the right sequence of learning concepts in a timely efficient way.

In particular, we propose the use of the memetic optimization theory embedded in a hierarchical distribution scenario to derive the fittest matching between learning paths and available learning activities in order to generate the best personalized e-Learning experiences.

More in detail, this paper proposes a novel parallel optimization algorithm based on multi-core processors capable of solving the PLP problem derived from the ontological representation of learning environments in a fast way, and at the same time, computing good quality learning experiences. Differently from previously proposed parallel evolutionary algorithms [7], our study exploits the hardware details of the genetic distributed systems in order to obtain a massive parallelism that speeds up the generation of personalized e-Learning presentations.

We will show, with experimental results, that our computational intelligence proposal can find suitable sub-optimal solutions with a smaller computational effort than pure genetic approaches and the generated results are able to improve the learning level of a generic learner.

The proposed paper is organized in three different parts. In the first part, a computationally efficient, hierarchical memetic solution for solving hard optimization problem is furnished; in the second part, an ontological e-Learning model together with an optimization problem characterizing the generation of best e-Learning experience binding is formalized; the last part shows the application of the proposed hierarchal memetic algorithms to an e-Learning environment together with the experimental results.

2 Related works

Today, the e-Learning specifications are based on educational metadata: IEEE LOM [8] and ADL SCORM [9], for example, are the standards proposed for describing piece of learning content annotated through metadata [10, 11]. Metadata is supposed to enable reuse of these chunks by detailing the conditions of their initial deployment [12]. However, some authors ([13, 14]) pointed out that such an approach failed to elicit cognitive behaviors and therefore actual reuse. We believe that the use of ontologies in e-Learning can overcome these drawbacks. Indeed, ontologies has been applied in different research fields [15–20] achieving optimal performances in the information exploitation. In [21], some benefits of applying ontologies to e-Learning are well explained. The authors asserts that an ontology, formally and declaratively, represents the terminology of a specific domain, defining its essential knowledge. Ontologies are used to support semantic search, making possible to query multiple repositories and discover associations, between Learning Objects, that are not directly understandable. This is impossible or very complex with simple keyword- or metadata-based search supported by the current standards. Blended learning is considered a learning approach defined by the effective combination of different modes of delivery and models of teaching and styles of learning [22]. Personalized e-Learning experiences represent a convenient way to complement face-to-face sessions within a whole blended learning experience. A personalized e-Learning experience could be very important when used for assessing the knowledge acquired by each individual learner during a face-to-face learning session and offering, in case of negative results, personalized remedial works able to fill the identified knowledge gaps with learning paths that best fits the needs, the cognitive state and the learning preferences of each individual learner. In the event that the personalized e-Learning experience can be built, packaged and deployed with an automatic process, then the whole blended learning activity can become more effective and efficient. Computational intelligence techniques are meaningfully exploited for providing intelligence and personalization in e-Learning environments [23, 24]. Buraga [25] proposes an agent-oriented extensible framework based on XML family for building a hypermedia e-Learning system available on the world-wide web. It deploys mobile agents that can exchange information in a flexible way via XML-based documents. The intelligent tutoring system is composed of four major components. The information processed by each component can be stored by XML documents. Some of the components have been implemented as intelligent agents. Angehrn et al. [26] suggests the use of K-InCA to provide a personalized e-Learning system. K-InCA is an agent-based system designed to assist people in adopting new behaviors. The agents within the system examine users actions and maintain a “behavioral profile” reflecting the level of adoption of the desired behaviors. Based on the user profile, and relying on a model borrowed from change management theories, the agents provide at different stages customized guidance, including mentoring, motivation or stimulus, in order to support real learning and smooth adoption of new behaviors. Zaiane [27] suggests the use of web mining techniques to build such an agent that could recommend on-line learning activities or shortcuts in a course web site based on learners access history to improve course material navigation as well as assist the online learning process. The automatic recommendation system takes into account profiles of on-line learners, their access history and the collective navigation patterns, and uses simple data mining techniques according to the service-oriented integration for e-Learning systems based on web services.

3 Generating personalized e-Learning experience through distributed memetic algorithm

This section presents a novel evolutionary algorithm to efficiently solve optimization problems by means of a hierarchical and parallel application of memetic techniques.

The evolutionary computation is a subfield of computational intelligence that involves methods for solving combinatorial optimization problems. These methodologies use iterative progress, such as growth or development in a population of candidate problem solutions. This population is then selected in a guided random search using parallel processing to achieve the desired end, i.e. the best solution for the given problem.

Evolutionary algorithms are evolutionary computation methods in that, generally, only involve techniques implementing mechanisms inspired by biological evolution such as reproduction, mutation, recombination, natural selection and survival of the fittest individuals. Candidate solutions to the optimization problem play the role of individuals in a population, and the optimization problem’s fitness function determines the environment within which the solutions “live”. Evolution of the population then takes place after the repeated application of the above operators. In this process, there are two main forces that form the basis of evolutionary systems: recombination and mutation create the necessary diversity and thereby facilitate novelty, while selection acts as a force increasing quality. Many aspects of such an evolutionary process are stochastic because, changed pieces of information due to recombination and mutation are randomly chosen. On the other hand, selection operators can be either deterministic, or stochastic. In the latter case, individuals with a higher fitness have a higher chance to be selected than individuals with a lower fitness, but typically even the weak individuals have a chance to become a parent or to survive.

The combinatorial optimization method presented in this paper, however, is a based on an innovative idea of evolutionary algorithm, memetic algorithms, that can be considered as an genetic algorithm’s extension. Indeed, memetic algorithms are evolutionary algorithms that apply a separate local search process to refine individuals (e.g. improve their fitness by hill-climbing or simulated annealing process). In the literature, memetic algorithms have also been named hybrid genetic algorithms (e.g. [28, 29]), genetic local searchers (e.g. [30]), Lamarckian Genetic Algorithms (e.g. [31]), and Baldwinian Genetic Algorithms (e.g. [32]). These methods are induced by models of adaptation in natural systems that combine evolutionary adaptation of populations of individuals with individual learning within a lifetime. They are inspired by Richard Dawkins concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement.

More in detail, from an optimization point of view, memetic algorithms are optimization methods that combine global and local search by using an evolutionary approach to perform exploration, while the local search method performs exploitation. Combining global and local search is a strategy used by many successful global optimization approaches, and memetic algorithms have in fact been recognized as a powerful algorithmic paradigm for evolutionary computing. In particular, the relative advantage of memetic algorithms over evolutionary algorithms is quite consistent on complex search spaces. As generic rule, the local optimization is applied at the end of each genetic iteration or at the end of the whole genetic process. This choice is strongly depending upon the problem definition. In our case, we have obtained better results by applying an a specific at the end of the whole process (see Sect. 6).

Our proposal tries to exploit memetic algorithms in a distributed way in order to speed-up the best solution convergence rate. In detail, the proposed approach exploits a hierarchical method of distribution based on multi-agent system. In detail, hierarchical memetic algorithms exploits an approach, in which, the emphasis is on getting agents to work together well to solve problems that require collective effort. Due to an inherent distribution of resources such as knowledge, capability, information, and expertize among the agents, an agent in a hierarchical system is unable to accomplish its own tasks alone, or at least can accomplish its tasks better (more quickly, completely, precisely, or certainly) when working with others.

Differently from other parallel genetic approach exploiting a computer network, our idea attempts to solve hard optimization problems by using a single multi-cores processor. This choice represents a right tradeoff between the quality of the solution and computational costs. Indeed, currently, the multi-core solutions represent the standard of microprocessors market and it allows our algorithm to be computed on a single low-cost computer without needing of complex and expensive grid computing environment. As shown in Sect. 6, this approach achieves a linear speed up (related to the number of cores) and, at same time, minimizes the hardware cost.

As will be shown in the following sections, the integration of hierarchical distribution with evolutionary approaches is exploited to derive the fittest matching between concepts within learning paths and available learning objects in order to generate the best personalized e-Learning experiences and, at the same time, minimize the computational effort necessary to compute the optimal matching. The benefits obtained from this hierarchical technique regard, mainly, the Web 2.0 support. In fact, Web 2.0 is characterized from a large number of information sources as blogs, wikis, podcasts and other web sharing applications and, in this case, the matching problem becomes too much complex to be solved with a typical sequential and deterministic algorithm.

The following sections will be devoted to present the proposed hierarchical method and its application to e-Learning environments together with experimental results showing that the multi-cores evolutionary approach we propose can find suitable solutions with a minor computational effort with respect to pure genetic algorithm approach and better solutions than pure parallel genetic algorithm with a comparable computational work.

3.1 A hierarchical model for distributed memetic algorithms

As shown in literature [33, 34], the parallel evolutionary models solve optimization problem achieving a considerable convergence rate speed up by means of a collection of computational hosts. The most used parallel evolutionary model are the Parallel Genetic Algorithms (PGAs) [35], an extensions of panmictic genetic algorithms. The well-known advantage of PGAs is their ability to facilitate speciation, a process for which different subpopulations evolve in diverse directions simultaneously. They have been shown to speed up the search process and to attain higher quality solutions to complex design problems [36–38]. In addition to the parallel panmictic GA, two popular parallel structured genetic algorithms include the island and cellular genetic algorithms [39]. The three basic models of PGA are:

• Master-slave PGA In master-slave PGAs, it is assumed that there is only a single panmictic population, i.e. a canonical genetic algorithm. However, unlike the canonical genetic algorithm, evaluations of individuals are distributed by scheduling fractions of the population among the processing slave nodes. Such a model has the advantage of ease of implementation, and does not alter the search behavior of a canonical genetic algorithm.

• Fine-grained or cellular PGA Fine-grained PGA consists of only a single population, which is spatially structured. It is designed to run on a closely-linked massively parallel processing system, i.e. a computing system consisting of a large number of processing elements, and connected in a specific high-speed topology. For instance, the population of individuals in a fine-grained PGA may be organized as a two-dimensional grid. Consequently, selection and mating in a fine-grained parallel GA are restricted to small groups. Nevertheless, groups overlap to permit some interactions among all individuals, so that good solutions may be disseminated across the entire populations. Sometimes, the fine-grained parallel GA is also termed as the cellular model PGA.

• Multi-population or multi-deme or island PGA A multiple population (or deme) PGA may be more sophisticated, as it consists of several subpopulations that exchange individuals occasionally. This exchange of individuals is called migration, and it is controlled by several parameters. Multi-population PGAs are also known by various names. Since they resemble the island model in population genetics that considers relatively isolated demes, it is also often known as the island model PGA.

These basic models need of advanced computer networking technologies to be computed as grid infrastructures for security, data management, resource management, and information service. These technologies require high computational and economical costs for being performed and, therefore, some tricks are necessary for minimizing of such efforts.

In this paper, an attempt of minimization of the aforesaid costs is introduced by considering the novel trend in the microprocessors market: the multi-cores technology. Indeed, the proposed optimization approach simulates a grid environment by using the different cores of a single processor.

In particular, the distributed memetic optimization is accomplished by exploiting a hierarchical methodology which splits the initial collection of candidate solutions on different processor cores, each one capable of applying the appropriate genetic operators in a parallel fashion and exchanging information about best chromosomes. From this point of view the processor’s cores can be viewed as computational entities performing a prefixed task. One of the most interesting features of the hierarchical optimization model that we propose, introduces a novel idea of distributed memetic algorithm whose behavior is depending upon the hardware configuration of the host computing it as can be seen in Fig. 1. This figure shows that our approach is capable of distributing the genetic computing on the different cores of a same processor, taking advantage by the generated parallelism.

Fig. 1

Hierarchical versus Not Hierachical Evolutionary Model

3.1.1 Hierachical memetic behavior

The hierarchical memetic algorithm exploits different properties coming from parallel genetic algorithm area. Indeed, our algorithm can be viewed as a hybrid approach merging together Master-slave with Island PGA. The idea is to split the population on the processor cores, to apply the genetic operator, to compute the best core solutions (the islands), to melt them together by means of a novel Gaussian-based approach and, finally, to apply local optimization to achieve high-quality solutions (the master).

More formally, the host that implements the hierarchical memetic behavior is capable of applying four elementary operations in a sequential way in order to solve a given optimization (minimization) problem:

• Hierarchical distribution among processor cores;

• Genetic operators: crossover, mutation and migration;

• Merging of the better solutions;

• Application of a local optimization method.

The hierarchical distribution is performed only if it is necessary, i.e. only if the system is composed by more than one single core. If pop is the initial chromosomes population associated with the problem and cores is the number of processor cores, then this behavior generates cores subpopulation, pop _j with j = 1,…,cores and it uniformly distributes the novel populations on the processor cores. Formally,

$$ pop=\bigcup_{j = 1}^{cores} pop_{j}. $$

(1)

Once received the subpopulation pop _j , the jth core applies genetic operators (selection, crossover and mutation) in a standard way in order to improve the fitness mean value of pop _j ; let μ _popj be this mean value. The hierachical algorithm uses the mean values μ _popj with j = 1,…,cores in order to choose the best chromosomes belonging to core populations. These chromosomes are chosen in a selective way by exploiting the following Gaussian distribution:

$$ \gamma_j(\mu_{pop_{j}}) = \left(\frac{{1}}{{\sqrt{2\pi}\cdot\sigma}} \exp\left(-\frac{{1}}{{2}}\left(\frac{{\mu_{pop_{j}} -\mu}}{{\sigma}}\right)^2\right)\right)\cdot\eta $$

(2)

where μ _popj is the mean fitness value coming from jth core, μ is the mean value, σ is the standard deviation and η represents a scaling factor. This formula computes, for each core j, the number of chromosomes that are candidates to pass to the next step of the algorithm; when the value μ _popj is close to the value μ then a large number of chromosomes will be selected and vice versa. The constant η can range in [0, + ∞[, if η assumes a value in [0, 1[ then the elitism level of the algorithm decreases by considering only a sub-set of the chromosomes computed by the pure Gaussian distribution, viceversa, for η in ]1, + ∞[ the elitism level of the algorithm increases by considering a larger chromosomes set.

Then, the number of candidate solutions to apply local search, best _j , is evaluated by multiplying the previous Gaussian value with the size of corresponding subpopulation, pop _j .

$$ best_{j} = \lceil \gamma_j \cdot pop_{j} \rceil. $$

(3)

Then the total number of chromosomes candidate for local optimization is:

$$ best = \sum_{j=1}^{cores} best_{j} $$

(4)

where best _j denotes the number of the best candidates coming from the jth cores. The choice of μ, σ, η has to be done with attention because this choice determines best _j value; these values are strongly depending upon the problem as it will be shown in Sect. 6. If best _j is small, then the related mean value is very high and the number of solutions candidate to improve their fitness is very small, vice versa, if best _j is large, then the related mean value is not very high meaning that the corresponding population contains a high number of chromosomes candidate to improve their quality.

As a sample, Fig. 2 shows a Gaussian chromosomes selection based on 4-cores processor and exploiting the Gaussian distribution:

$$ \left( \frac{{1}}{{\sqrt{2 \pi}\cdot 1.2}} \cdot {\rm e}^{-\frac{{1}}{{2}}\left(\frac{{\mu_{pop_j} -40.783}}{{1.2}}\right)^2}\right) \times 3 $$

(5)

where μ = 40.783, σ = 1.2 and η = 3. Now, if pop ₁ = pop ₂ = pop ₃ = pop ₄ = 25 and μ_pop1 = 36.2, μ_pop2 = 38.4, μ_pop3 = 39.2 and μ_pop4 = 40.40, then:

$$ \begin{aligned} best_1 &= 0 \cdot 25 = 0;\\ best_2 &= \lceil0.1388 \cdot 25\rceil = 4;\\ best_3 &= \lceil0.4178 \cdot 25\rceil = 11;\\ best_4 &= \lceil0.95 \cdot 25 \rceil = 24. \end{aligned} $$

Fig. 2

The 4-cores Gaussian distribution sample

Once computed the best chromosomes, the algorithm applies a further genetic evolution by using as population the best of the bests chromosomes coming from the cores. Then, the fittest solution coming from this operation is exploited by a local search optimization procedure able to ulteriorly improve the quality of solutions. Some of the most used local optimization methods are the simulated annealing and the gradient method. However, in this paper, we will define an ad hoc local search algorithm capable of maximizing the probability of solutions improvement. Following subsections will be devoted to introduce the e-Learning concepts that define an optimization problem used to derive the best learning experiences for a given learner group.

4 The e-Learning system

In this section, the different parts composing the proposed e-Learning system and their relationships are presented. The foundation of the e-Learning system is the Learning Model [40]. The Learning Model allows to automatically generate a Unit of Learning (i.e. a course, a module or a lesson structured as a sequence of Learning Activities represented by Learning Objects and/or Learning Services) [41] and to dynamically adapt it during the learning process according to the learners preferences and cognitive state (personalization process). A Unit of Learning (UoL), during its execution, represents what we have previously named e-Learning experience.

From a conceptual viewpoint (see the Fig. 3), we can see the Learning Model as realized across two layers. The first one is the Knowledge Layer, in which there are all the machine-understandable representations of the relevant entities (e.g. educational domains, learning objects, learners, etc.) we use in our approach. The second one is the Computational Layer in which there are a set of algorithms acting upon the first layer in order to execute the personalized e-Learning experiences building process (also executed in order to construct remedial works). Teachers interact with the abstractions of the Learning Model providing artefacts (e.g. ontologies, learning objects, etc.) at the Knowledge Layer. Students interact with the abstractions of the Learning Model providing (implicitly or explicitly), at the Knowledge Layer, information about their own characteristics.

Fig. 3

Conceptual architecture of the e-Learning system

In order to achieve the expected adaptation capability, the Learning Model uses three specific sub-models: the Knowledge Model, the Learner Model and the Didactic Model, which are exploited by a specific process used to define personalized e-Learning experiences. The three sub-models taken into account are, respectively: the knowledge about educational domains (e.g. Mathematics, Chemistry, Java-Programming and so on), the context where the educative processes occur; the learning method and style to apply; the learners preferences and cognitive states; and, finally, the learning objectives. In particular, the Didactic Model defines the modalities provided by the UoL to the learners in order to enable them to acquire knowledge about a specific educational domain. In a personalized e-Learning experience, these modalities depend, above all, upon the selected educational domain, the learner’s learning style and the context. In the following subsections, we give detailed descriptions of the Knowledge Model and the Learner Model, but, for sake of simplicity, we disregard the Didactic Model which is not fundamental for the focus of this work.

4.1 The Knowledge Model

The Knowledge Model describes, in a machine-understandable way, the piece of the educational domain that is relevant for the e-Learning experience we want to define, concretize and broadcast. The mechanism used by the Knowledge Model is named ontology, i.e. an engineering artifact, constituted by a specific vocabulary used to describe a certain reality, plus a set of explicit assumptions regarding the intended meaning of the vocabulary words [42]. In our approach, vocabularies are composed by terms representing subjects that are relevant for the frame of the educational domain we want to model. Subjects are associated to other subjects through a set of three conceptual relations: HasPart (in brief HP) that is a part-of relation, IsRequiredBy (in brief IRB) that is an order relation and SuggestedOrder (in brief SO) that is a “weak” order relation. The ontologies constructed following the few aforementioned informal rules are named e-Learning ontologies. You take care that when we refer to concepts in e-Learning ontologies we are referring to the subjects of the educational domain we are modeling. Now, in order to illustrate how to build an e-Learning ontology, let us suppose we have to model the educational domain D, so the first step is to conceptualize the knowledge underlying D and find a set of terms representing relevant concepts in D. The result of the previous step is the list of terms T = C, C ₁, C ₂, C ₃ where T is one of the plausible conceptualizations of D. In order to explain the semantics of the HasPart conceptual relation, we can refer to ontology illustrated in Fig. 4a where the three HasPart (extensional) relations HasPart(C, C ₁), HasPart(C, C ₂) and HasPart(C, C ₃) means that learners have to learn subjects C ₁, C ₂ and C ₃ for the learning subject C without considering a specific order.

Fig. 4

a Semantics of HasPart. b Semantics of IsRequiredBy

Now, consider the ontology shown in Fig. 4b. This ontology presents two IsRequiredBy (extensional) relations, IsRequiredBy(C ₁, C ₂) and IsRequiredBy(C ₃, C ₂). The two relations mean that C ₁ has to be necessarily learned before C ₂ and C ₃ has to be necessarily learned before C ₂.

Last, suppose that we add a SuggestedOrder relation between concept C ₁ and concept C ₂ in the ontology of Fig. 4a, i.e. we set the relation SuggestedOrder(C ₁, C ₂). In this case, we are stating that it is preferable to explain subject C ₁ before subject C ₂, but this is not mandatory.

After we have described the simple rules used to model educational domains, we are going to explain how to model learners’ characteristics in order to personalize his/her learning experiences.

4.2 The Learner Model

Learner is the main actor of the whole cognitive process and he/she has to be represented in a machine-understandable way in order to support the personalization process of the e-Learning experiences. The Learner Model states which are the learner properties [43] to model and the way we can represent them. In particular, every learner is represented by his/her cognitive state and by the set of his/her learning preferences.

The cognitive state representation reports a measure about the knowledge acquired by a learner at a given time and it is represented by a list of subjects (concepts within e-Learning ontologies) that the learner has encountered during the execution of one or more learning experiences. In the aforementioned list, each subject is associated with a grade whose values (real numbers) are taken from the interval [0, 1], where 0 testifies the complete absence of acquired knowledge with respect to a given subject, while 1 tells us that there is an optimal knowledge about the specific subject. A subject will be considered as “learnt by the learner” if the above defined grade is greater than a previous fixed threshold (fixed by experimentations). It’s important to underline that the grade, held by a learner for a given subject, is not constant in the time but it can vary depending on the assessment results of the learner. The assessment phases, realized by several kind of tests (e.g. multiple choice test, etc.) are embedded into e-Learning experiences and are used to assess learner knowledge about studied subjects.

The learning preferences state is represented by a list of couples as:

$$ (property name, property value) $$

For sake of simplicity, we consider that properties are contained in the set (Learning Resource Type, Interactivity Type, Interactivity Level, Typical Learning Time, Difficulty, Language, Context). The table in Fig. 5 reports the values that are admissible for each property.

Fig. 5

Admissible values for properties in learning preferences

The properties in a learning preferences state declare the properties that learning resources (learning objects or learning services) should have in order to fit with the learner’s characteristics and thus achieving the most effective and efficient learning process. For instance, if a learner has a learning preferences state represented by a tuple as

$$ \{Simulation, Active, High, 5 minutes, Medium, IT, Higher Education\} $$

then we can state that he/she learns better using computer simulations (eventually implemented with Flash [44] or Silverlight [45] technologies) where the human-interaction is prevalent, is prepared for high schools students, presents not many parameters, communicates in italian language and that takes about 5 min to be enjoyed.

Last, note that the bootstrapping for learning preferences and cognitive state of each learner could be realized through the adoption of a self-assessment phase and there is not the necessity to set values “by hands”.

4.3 Defining personalized e-Learning experiences

The aforementioned Learning Model allows the construction of personalized e-Learning experiences through the execution of a building process based on some related algorithms. These algorithms have been implemented in a running system product namely Intelligent Web Teacher (IWT) [46–48]. Using these algorithms, it is possible to generate courses tailored to a class, to a specific group and even to single learners. In the following, we provide details about the process and how the algorithms perform an evolutionary/memetic computation in order to define it. In particular, we present the steps for the creation of an e-Learning experience tailored to a single user’s preferences. For the sake of simplicity, we will consider that an e-Learning experience is represented by a sequence of learning objects, but the approach is also suitable when e-Learning experiences are made up of complex ows of learning activities.

Before going deeply into the details of the algorithms related to the personalized e-Learning experiences building process, we have to illustrate how learning objects and e-Learning experiences are related to Knowledge Model and Learner Model within the whole Learning Model.

A learning object is defined, by IEEE 1484.12.1–2002 [49], as “an entity, digital or non-digital, that may be used for learning, education or training”. The main idea of learning objects is to break educational content down into small chunks that can be reused in various learning environments. In order to allow the re-use of learning objects, they have to be annotated with metadata (e.g. author, keywords, description, etc.). The most used metadata schema, able to support the annotation of learning objects, is the Learning Object Metadata (LOM) developed by IEEE. In our approach, a learning object is a learning content (or a packaged aggregation of learning content) that can be delivered through a Web Browser, that is annotated with an instance of a metadata schema (interoperable with IEEE LOM) and that is stored and indexed into a Learning Object Repositorie. Learning Object Repositories provide Application Program Interfaces (API) for retrieving learning objects by their metadata. Exploiting the aforementioned API we can get, for instance, all existent learning objects whose metadata states that the learning object description contains the word maths. Furthermore, a single learning object can be associated to an e-Learning ontology through a metadata field, namely subjects list, that memorizes references to all subjects, coming from one or more ontologies, explained by the learning object content. For the sake of clarity, we assume that the metadata fields (other than subjects list) are the same of those used for describing learning preferences in 2, i.e. (Learning Resource Type, Interactivity Type, Interactivity Level, Typical Learning Time, Difficulty, Language, Context). The vocabulary used for the metadata fields is the same of that one reported in Fig. 5.

Let us see Fig. 6 in order to have some additional hints about the semantic link between learning objects and the concepts (subjects) of an e-Learning ontology. First of all, it is possible that the same learning object can explain more than one subject within the same ontology. This is the case of learning object LO ₂ that explains subjects C ₂ and C ₃. Otherwise it is possible to have more than one learning object explaining the same subject. This is the case of LO ₄ and LO ₅ both covering the subject C ₄. This is true also for LO ₂ and LO ₃ both covering subject C ₃ even if LO ₂ explains also the subject C ₂. In order to simplify future discussions, we can define the relation Explain(LO, C) which states that the learning object LO explains the subject C.

Fig. 6

Semantic link between learning objects and e-Learning ontologies

4.3.1 The UoL building process

e-Learning experiences are defined as: (i) a set of Target Concepts (TC), i.e. the set of high-level concepts to be transmitted to the learner; (ii) A Learning Path (LP), i.e. an ordered sequence of atomic concepts (subjects) that is necessary to explain to a learner in order to let him/her learn TC. Given the personalization on a particular learner, the sequence does not contain subjects already “learnt” (i.e. known with a grade greater than the fixed threshold, as we have seen in 2) by that learner; (iii) A Presentation (PR), i.e. an ordered list of learning objects that the learner has to use in order to acquire knowledge about subjects included in LP.

LP can be automatically obtained starting from TC, while PR can be automatically constructed starting from LP and querying (using metadata information) one or more Learning Object Repository. TC can be settled by the teacher or directly by the student (in case of self-directed learning) and can be obtained by manually selecting concepts on ontologies or by selecting pre-defined groups of concepts (Figs. 7, 8).

Fig. 7

State of a sample learning object repository

Fig. 8

Cognitive state and learning preferences of John

Excluding the selection of TC and other customization parameters, the building process is fully automatic and realized through the execution of several algorithms. The most important are: Learning Path Generation Algorithm and Presentation Generation Algorithm. The first one determines the ordered sequence of atomic concepts needed to reach a satisfactory knowledge about selected TC on the basis of a reference e-Learning ontology, a set of TC and a given cognitive state. The second one selects and orders a set of learning objects, explaining all the concepts in the Learning Path, that best fits with the given learning preferences state. The algorithm acts to minimize the number of learning objects (remember that a single learning object could explain more than one adjacent subjects into the same LP) within the Presentation that are necessary in order to cover the whole Learning Path.

Let us see a simple example before going ahead. Consider again the situation of Fig. 6 when the e-Learning System has to define a personalized e-Learning experience for a learner namely John (Fig. 7 reports metadata of learning objects available into the Learning Object Repository, while eight reports cognitive state and learning preferences state of John) and suppose that TC = C. Then the Learning Path Generation Algorithm extract the following personalized Learning Path LP(TC) = [C ₃, C ₂, C ₄]. Note that subject C ₁ in already “learnt” by John, so it has been deleted from the path. At this point, the Presentation Generation Algorithm performs a binding between available learning objects and subjects in LP. In particular, the binding must try to minimize the number of learning objects and select the learning objects whose metadata satisfy better the learning preferences of John. In our example, PR = [LO ₂, LO ₄]. In particular, LO ₄ is preferred to LO ₅ because the second one does not match with John’s learning preferences.

Once the presentation (for a given student) is ready, it is packaged into a Unit of Learning (UoL), then the enrolled student can start his/her execution phase. The student accesses the Presentation (through an application able to interpret and deliver the UoL in a Web Browser) and executes the proposed activities studying the sequence of learning objects provided by the system until a milestone (assessment point within the LP) is reached. At this point, the student executes the assessment phase and the results are sent to the system. At this point, the learner cognitive state is updated on the basis of latest assessment results. The sequence of the previously described algorithms is now re-executed considering the evolution of the learner cognitive state. In this way, a mechanism to assemble personalized remedial works is provided. The learning process of a student ends when his/her cognitive state reports that all subjects of the LP have been learnt.

4.3.2 The Presentation Generation Algorithm

For sake of simplicity, we disregard the Learning Path Generation Algorithm and suppose to have already extracted the personalized LP (or simply LP) using a sequence of graph algorithms applied on the reference e-Learning ontology. Starting from the extracted LP, the Presentation Generation Algorithm has to select, from one or more Learning Object Repositories, an optimal set of learning objects in order to cover the ordered set of subjects within the LP. This problem can be formulated as a Plant Location Problem on a bipartite graph as shown in Fig. 9.

Fig. 9

Formalization of plant location problem in e-Learning context

In the situation depicted in Fig. 9, we have three learning objects to use in order to explain a set of four subjects. There is an arrow between a learning object LO _i and a subject C _j only if the metadata instance of LO _i includes a semantic link to the subject C _j (i.e. its subjects list field contains Explain(LO _i , C _j )).

For each couple (LO _i , C _j ) linked in the bipartite graph, there is an assigned value d(i, j). The value d(i, j) represents the distance between LO _i and C _j . Short distances define good coverings. Furthermore, to each learning object, LO _i is associated a value p(i) representing the cost of the introduction of the learning object LO _i into the PR. Let us assume that distances d(i,j) are calculated applying a specific function that evaluates the matching between the metadata values of LO _i covering C _j and the learning preferences of the learner who requests the personalized e-Learning experience.

Now, consider m as the number of learning objects available and n the number of subjects in the Learning Path to be filled. In order to formally introduce the PLP problem whose solution represents the mapping between learning objects and concepts, it is necessary to introduce two mathematical entities, a vector y and a two-dimensional matrix x where the assignment y _k = 1, means that a given problem solution uses the learning object LO _k and the assignments x _kj = 1 and x _kh = 0 for h ≠ j mean that the learning object LO _k covers the concept C _j .

Thus, the linear programming model which formalizes the whole problem can be described as follows:

$$ \hbox{min} \sum_{i=1}^{m}p(i)y_i + \sum_{i=1}^{m}\sum_{j=1}^{n}d(i,j)x_{ij} $$

(6)

s.t.

$$ \begin{aligned} &\sum\limits_{j=1}^{n} x_{ij} = 1 \quad i=1,{\ldots}, n \\ &x_{ij} \leq y_i \quad i=1,{\ldots}, m, \quad j=1,{\ldots}, n\\ &x_{ij} \in \{0, 1\} \quad i=1,{\ldots}, m, \quad j=1,{\ldots}, n\\ &y_i \in \{0, 1\} \quad i=1,{\ldots}, m \end{aligned} $$

The optimal solution of the Plant Location Problem means the identification of the optimal set of learning objects that better match (minimal distance) the learner preferences. The constraints:

$$ \begin{aligned} &\sum\limits_{j=1}^{n} x_{ij} = 1, \quad i=1,{\ldots}, n \\ &x_{ij} \leq y_i, \quad i=1,{\ldots}, m \quad j=1,{\ldots}, n \end{aligned} $$

(7)

have to be satisfied to guarantee that each learning concept will be exactly covered by a one only learning object.

Although some special cases of the SPLP are solvable in polynomial time, in general, a Plant Location Problem is a NP-hard problem. Genetic algorithms are typically used to solve some NP-hard problems and recent researches show that combination of genetic algorithm and local search can be successful in solving NP-hard problems.

Now, it is important to make some considerations about the approach we have proposed before:

• The e-Learning System improves the learning quality, in terms of personalization and consequently of efficiency and effectiveness of provided learning processes, grow up as the number of available learning objects is increased. This is clear considering that having more available learning objects means that there are more opportunities to better satisfy the learners’ preferences.

• The raising of numerous IEEE LOM-compliant Learning Object Repositories [51] (e.g. MERLOT [52] with 10,607 public objects stored, eRIB [53] with 49,761, EdNA Online [54] with 30,300 public objects stored, etc.) can significantly improve the quality of the proposed approach if we consider an architecture (see Fig. 10) where the e-Learning System is able to access several repositories distributed over the Web through specific connectors. In order to construct a reliable centralized index of learning objects scattered over the set of repositories, we can use some techniques coming from Web 2.0. In particular, standard publication languages like RSS [55] can be used to simplify the information passing between the nodes of the distributed architecture. Repositories publish their content using RSS feeds and the e-Learning System maintains its index constantly up-to-date through the use of RSS feeds aggregators.

• The increase of the available learning objects number has a remarkable impact on the performance of the Presentation Generation Algorithm.

Fig. 10

Distributed learning object repositories architecture for the e-Learning system

In the following sections, that are the core of this work, we will define a new distributed and high scalable Presentation Generation Algorithm, based on a novel optimization paradigm merging the memetic theories together with the hierarchical multi-cores methodologies. This approach is suitable to face the emergency caused by the growing of the available learning objects number when we want to exploit an e-Learning System Open Architecture where the available repositories can be added at run-time by plugging specific connectors.

It’s important to underline that the exploitation of several Learning Object Repositories and their distribution over the Internet do not affect our modeling of the binding problem (learning objects used to cover subjects into the Learning Path) as a Plant Location Problem. In this case, the cost p(i) payed to add learning object LO _i to the PR can be defined also in terms of the location of LO _i (for instance, lower costs can be assigned to learning objects stored into local repositories, otherwise higher costs can be assigned to learning objects stored into remote repositories).

5 Applying the hierarchical memetic algorithm to e-Learning scenario

As shown in previous section, our e-Learning system defines the PLP optimization problem whose solution associates a collection of didactic concepts to a set of learning objects. The weight of the arcs connecting concepts and learning objects are defined by exploiting the user learning preferences, whereas, the concept costs is derived from a combination of multiple factors. When our approach is used to model an e-Learning 2.0 scenario, the related PLP problem becomes too much complex to be solved through a deterministic approach or a sequential evolutionary algorithm. In this section, the hierarchical memetic model defined in the previous section will be applied to e-Learning PLP problem by defining the chromosome template, the collection of genetic operators exploited by cores, the local search strategy and the set of Gaussian distribution parameters used to derive the best matching among learning objects and didactic activities.

In order to solve this PLP problem, it is necessary to fix different genetic properties and parameters involved in the evolutionary schemas. In detail, we have to define (i) how to represent a potential problem solution, i.e. a chromosome, (ii) the genetic operators to exploit in order to run genetic evolutions and (iii) the fitness function indicating how good are the solutions computed by the algorithm. As previously stated, a solution of defined problem is given by the optimal allocation of m didactic objects to n learning concepts where each concept has to be covered by one and only one didactic activity. In other word, a chromosome L can be defined as a numerical vector composed whose n components (genes) range in the [1, m], where the ith components l _i = j means that the jth learning concept is covered by the ith learning object (i.e. p(i) = 1 and d(i,j) ≥ 0). In this way, the problem fitness function (to minimize) is:

$$ fitness(L) = \sum_{i=1}^{m}p(i) + \sum_{i=1}^{m}\sum_{j=1}^{n}d(i,j) $$

(8)

with a one only constraint: if c is a given chromosome and, c[i] and c[j] with j > i are two learning objects related with concept i and j and c[i] = c[j] then, necessarily, it must be j = i + 1. In order to test the solution feasibility necessary are O(n ²) computational steps, where n is the chromosome size. In fact, the constraint can be checked only by analyzing each of n ² gene pairs. If we suppose that the number of individuals and the number of genetic iterations are close to n, then the total computational time needs to check the chromosomes feasibility is O(n ⁴) with a very large value of the hidden constant (depending upon the number of genetic evolutions). Even though this time is polynomial, it is too high to build an efficient sequential genetic algorithm. Then, the e-Learning PLP constraint is a further motivation about the exploitation of a distributed evolutionary approach. Figures 11 and 12 show, respectively, a sample of feasible and not feasible chromosome.

Fig. 11

Not feasible chromosome sample (m = 6, n = 8)

Once defined the chromosome template, it is possible to introduce the crossover and mutation operators exploited by each core to evolve its subpopulation portion. Proposed genetic algorithm uses a typical one-point crossover applied with probability $P_{crossover} =\frac{{1}}{{PopulationSize}}$ and, at same time, the algorithm uses a classical mutation operator applied with probability $P_{mutation} =\frac{{1}}{{n}}$.

The proposed parallel algorithm computes a feasible solution in a rapid way. Moreover, the solution quality is improved regarding the sequential evolutionary approaches because our proposal raises the speciation level of initial population through a hierarchical distribution. However, in order to further refine the quality, the supervisor can improve the parallel genetic solution by means of an appropriate local search process. In particular, each genetic host compute a sub-optimal population through the Gaussian function presented in previous section and, successively, the supervisor merges together the distributed sub-populations and, iteratively, applies a local refinement on chromosomes composing the merged population.

First step is to define, for a given feasible solution, the solution neighborhood, i.e. a set of feasible solution that are close to current solution. The local search operator exploits the neighborhood to improve the actual sub-optimal solution. Let L =  (l ₁, l ₂, l ₃,…,l _n ) ∈ {1,…,m}ⁿ be a current feasible solution belonging to merged sub-populations. In our e-Learning context, neighborhood N(L) is computed as the collection of solutions obtained by adding, removing or deleting a concept to L. Of course a (n + 1)-tuple (l ₁, l ₂,…,l _i−1, l _i , l _i ′,…,l _n ) ∈ {1,…,m}ⁿ⁺¹ obtained by adding a concept l _i ′ to the n-tuple L ∈ {1,…,m}ⁿ solution is not a feasible solution. Similarly, a (n−1)-tuple (l ₁, l ₂,…,l _i−1, l _i+1,…,l _n ) ∈ {1,…,m}ⁿ⁺¹ obtained by removing a concept l _i from the n-tuple L ∈ {1,…,m}ⁿ solution is not a feasible solution. Aim of local search operator is to explore N(L) in order to improve the current solution L by selecting a feasible solution better than L.

In detail, let L = (…,l _i−1, l _i , l _i+1, …) be a feasible solution coming from the genetic cores and let L′ =  (…,l _i−1, l _i ′, l _i+1, …) be the solution obtained by the local search process. Different cases have to be considered:

• 1. l _i ′ ≠ l_i−1, l _i ′ ≠ l_i+1 and l_i−1 ≠  l_i+1 (l _i ′ is not present in the remaining part of the chromosome), with fitness(L′) < fitness(L)

• 2. l _i ′ = l_i−1 and l _i ′ ≠ l_i+1 with fitness(L′) <  fitness(L)

• 3. l _i ′ ≠ l_i−1and l _i ′ = l_i+1 with fitness(L′) <  fitness(L)

• 4. l _i ′ ≠ l_i−1, l _i ′ ≠ l_i+1 andl_i−1 ≠  l_i+1 (l _i ′ is not present in the remaining part of the chromosome), with fitness(L′) > fitness(L)

• 5. l _i ′ = l_i−1 and l _i ′ ≠ l_i+1 with fitness(L′) >  fitness(L)

• 6. l _i ′ ≠ l_i−1and l _i ′ = l_i+1 with fitness(L′) >  fitness(L)

• 7. l _i ′ ≠ l_i−1, l _i ′ ≠ l_i+1 and l_i−1 =  l_i+1, with fitness(L′) < fitness(L)

It is clear that the solutions 1., 2., 3. are feasible and optimal solutions, the solution 4., 5., 6. are feasible but not optimal solutions and the solution 7. is an optimal but not feasible solution. In short, starting from solution L and by applying the replacing of activity l _i with l _i ′, we obtain better solution with probability $P = \frac{\text{number of feasible and optimal solutions}}{{\text{number of solutions}}}=\frac{3}{7} = 0.4285,$ i.e. each two refinement steps. the solution improves with high probability.

Once defined the L-neighborhood, it is possible to design the local search algorithm (listing 2).

6 Experimental results and conclusions

The paper introduces an innovative methodology to find an optimal personalized learning activity through the solution of a well-known NP-hard problem, the Plant Location Problem. This section presents the results obtained by the application of our methodology. These outcomes, however, could be evaluated from two different perspectives: a computational view where the focus is on the computational effort and the solution quality computed by our hierachical memetic algorithm; a learning view highlighting the benefits of proposed framework as an add-on in on-line learning.

6.1 A computational view

This section is devoted to compare the performance of a typical sequential genetic algorithm with our proposal of hierarchical memetic approach in term of both computation time and solution fitness. The programs implementing aforesaid algorithms were coded in Java programming language. The JGAP [56] library has been exploited to implement the program genetic features, whereas, the Fracture [57] library has been used to distribute the genetic computing on the different cores of processors. The simulation were carried out on a AMD Dual Opteron(tm) Dual Core (Quad Core) 2.40 GHz hosts, equipped with 2 Gb of RAM and running the Microsoft Windows XP × 64 operating systems. Our benchmark solves eight different PLP problems by using eight different matrixes with following size:

• 200 × 40 = 8,000;

• 400 × 80 = 32,000;

• 500 × 120 = 60,000;

• 750 × 180 = 135,000;

• 900 × 220 = 198,000;

• 1,000 × 270 = 270,000;

• 1,300 × 300 = 390,000;

• 1,600 × 500 = 800,000;

Each PLP problem is computed by exploiting, in sequence, one core, two cores, three cores and four cores. Then, our benchmark compares 32 different results (time and fitness). Moreover, the benchmark exploited the following parameter values: PopulationSize = 1000, MaximumNumberOfEvolutions = 100. Moreover, the Gaussian function exploits the following parameters to select the best chromosomes from core subpopulations: μ = 40.783, σ = 1.2, η = 3. In order to evaluate the algorithms, several criteria measuring the solution quality and computation time have been adopted. Multi-Core Time Performances (Fig. 13) represents the computation times expressed in milliseconds upon the algorithm termination. Fitness Ratio Comparison (Fig. 14) is the ratio between the fitness values obtained from the simulation computed by using a single core of a processor and the complete set of cores: in the ideal situation, this diagram would have to show a constant value equals to 1, i.e, both single core and multi-cores algorithms should compute the same optimal solution, however, as can be view in the figure this fitness ratio is always in the range [0.9, 1.0] proving that our hierarchical algorithm computes high-quality solutions very close to a single-core algorithm that simultaneously can work on the whole collection of chromosomes.

Fig. 12

Feasible chromosome sample (m = 6, n = 8)

Fig. 13

Multi-core time performances

Fig. 14

Fitness ratio comparison

Delta time comparison (Fig. 15) represents the difference between the time values obtained from the simulation computed by using a single core of a processor and the complete set of cores.

Fig. 15

Delta time comparison

Once computed the optimal matching among learning objects and concepts, it has been noted a considerable learning speed-up that will be quantified in a precise way in the following subsection.

6.2 Learning view

A small-scale experimentation was performed to demonstrate the benefits of our optimization system as an add-on in on-line learning. Such experimentation involved a group of 28 voluntary learners belonging to 7 small and medium enterprises dealing with vocational training on enterprise management. The group of learners was split in two separate sub-groups: a first sub-group composed of 20 learners was enabled to use all e-Learning facilities except memetic optimization while a second sub-group composed of eight learners was enabled to access the whole systems (including hierarchical memetic algorithm). All the voluntary learners were tested before and after a training phase on the same topics. In all the tests, the learners skills in the chosen domain were quantified using three ability ranges: low-level (0–3 scores), medium-level (4–7 scores) and high-level (8–10 scores). The Fig. 16 shows the performances of the two sub-groups. As it can be seen, the progress made by the second group of students is much sharper with respect to the first group.

Fig. 16

Experimentation results on a group of 28 learners with and without the proposed memetic framework

As shown, the proposed ontological/memetic distributed platform provides an integrated approach towards achieving the personalization in e-Learning environments. Our proposal enhances significantly the overall system in terms of flexibility and efficiency while it introduces a high degree of e-Learning platforms interoperability by utilizing ontology-based representation. The presented hierarchical algorithm supports various personalization levels (intended as most fitting sequences of learning activities able to maximize the understanding level of learners with respect to specific learning objectives) exploiting machine-understandable representations of educational domains and learners characteristics. The computational intelligence methodologies and, in particular, the memetic algorithms have been exploited to solve the e-Learning Plant Location Problem in fast way allowing system designers to realize an efficient in-time learning environment.