Marcin Stachowiak

Łukasz Jeleń

Lukasz Jeleń
email: lukasz.jelen@pwr.edu.pl

Automatic Segmentation Framework for Fluorescence in Situ Hybridization Cancer Diagnosis

Keywords: FISH, pattern recognition, image processing, computer aided diagnosis, breast cancer, nuclei segmentation, HER2, dot counting, SOM, PCA

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

According to the data provided by the National Cancer Registry, breast cancer is one of the most often diagnosed cancers among middle-age women [1]. Just in Poland, before 2016, there were 17144 diagnosed cases of breast cancer. This number is increasing year after year. For instance, between 2009 to 2012 there was an increase of 1280 diagnosed cases. The same records show that out of 17144 cancer cases there were 5651 deaths in 2012 which is 341 more than in 2009. Most of these cases could have been fully recovered if the diagnosis would be made in the early stage of the disease, because cancers in their early stages are vulnerable to treatment. To reduce the number of deaths it is crucial to perform a reliable and fast diagnosis that will allow for the determination of an appropriate treatment. For this purpose when a suspicious growth is found during the screening mammography tests a fine needle aspiration biopsy (FNA) or a core biopsy (CB) is taken. During these examinations a small sample from the questionable breast tissue is extracted and a prognostic factor is evaluated according to the so called Bloom-Richardson scheme [START_REF] Bloom | Histological Grading and Prognosis in Breast Cancer[END_REF]. This procedure, called a malignancy grading, allows the pathologist to describe the type of cancer in detail and estimate its behavior with or without undertaking treatment. Sometimes, when a difficult case is under diagnosis, the above techniques might require additional tests. This is why, for a more accurate diagnosis, a set of different examinations are performed. They will test for the presence of a HER2 gene and HER2 receptors that stimulate the growth of cancer cells. HER2 expression plays an important role in breast cancer diagnosis and the appropriate treatment is chosen accordingly to its status [START_REF] Hicks | Standardized assessment of the her2 status in breast cancer by immunohistochemistry[END_REF]. To determine the status of breast cancer biomarker such as human epidermal growth factor receptor 2 (HER2) a routine ImmunoHistoChemistry (IHC) or Fluorescence in situ hybridization (FISH) tests are performed.

-ImmunoHistoChemistry -is a staining process that shows if HER2 receptors and hormone receptors are present on the surface of the cancer cells (see Fig. 1a). This test helps in identification of the antigens in cells. This is possible due to binding of antibodies to the proteins. The final diagnosis is based on the estimation of different markers that may appear within and around the tumor cells [START_REF] Dana | Significance of immunohistochemistry in breast cancer[END_REF]. -Fluorescence in situ hybridization -is a test that allows for a visualization of genes, in this case HER2 gene [START_REF] Kiszler | Semi-automatic fish quantification on digital slides[END_REF] (see Fig. 1b). In breast cancer diagnosis it is used to determine if the cancer cells have additional copies of that gene. The rule here is that the more genes one can distinguish, the more HER2 receptors the cells have.

According to the American Society of Clinical Oncologists (ASCO) and College of American Pathologists (CAP) [START_REF] Ji | Clinicopathological variables predicting her-2 gene status in immunohistochemistry-equivocal (2+) invasive breast cancer[END_REF][START_REF] Slamon | Use of chemotherapy plus a monoclonal antibody against her2 for metastatic breast cancer that overexpresses her2[END_REF], also known as ASCO/CAP, the complete FISH examination also requires estimation of chromosome 17 centromere enumeration probe (CEP17 or CEN-17) [START_REF] Tibau | Chromosome 17 centromere duplication and responsiveness to anthracycline-based neoadjuvant chemotherapy in breast cancer[END_REF]. The final diagnosis is based on the HER2 to CEN-17 ratio [START_REF] García-Caballero | Determination of her2 amplification in primary breast cancer using dual-colour chromogenic in situ hybridization is comparable to fluorescence in situ hybridization: a european multicentre study involving 168 specimens[END_REF].

According to Hicks and Kulkarni [START_REF] Hicks | Her2+ breast cancer: Review of biologic relevance and optimal use of diagnostic tools[END_REF], both of the above tests are equivalent for the evaluation of the breast cancer HER2 status. In this study we are focusing on the FISH examination. As reported in literature [START_REF] Lerner | Automatic signal classification in fluorescence in situ hybridization images[END_REF][START_REF] Netten | Fluorescent dot counting in interphase cell nuclei[END_REF][START_REF] Tanke | Ccd microscopy and image analysis of cells and chromosomes stained by fluorescence in situ hybridization[END_REF], the problem of distinguishing the HER2 and CEN-17 reaction within the FISH slides is not an easy task. The main problem here is a segmentation of the reactions, where the HER2 reactions are visible in the image as red dots while the CEN-17 are detectable as green dots. Due to a small size of the regions of interest there is a need to find the best possible segmentation algorithm that will be able to localize both kinds of dots within the slide. Here, we took an opportunity to test two techniques that will be appropriate for this challenging task. Automatic cancer nuclei detection and segmetnation from medical images has been widely studied in the literature [START_REF] Cheng | Computer-aided detection and classification of microcalcifications in mammograms: A survey[END_REF][START_REF] Moghbel | A review of computer assisted detection/diagnosis (CAD) in breast thermography for breast cancer detection[END_REF]. One can find various reports on applying different imaging techniques [START_REF] Filipczuk | Computer-aided breast cancer diagnosis based on the analysis of cytological images of fine needle biopsies[END_REF][START_REF] Nagarajan | Classification of small lesions on dynamic breast mri: Integrating dimension reduction and out-of-sample extension into {CADx} methodology[END_REF][START_REF] Velikova | On the interplay of machine learning and background knowledge in image interpretation by bayesian networks[END_REF], segmentation methods [START_REF] Kowal | Nuclei segmentation for computer-aided diagnosis of breast cancer[END_REF] or classification approaches [START_REF] Filipczuk | Classifier ensemble for an effective cytological image analysis[END_REF] to solve this problem. In this study we are concerned on the segmentation of the FISH image to help doctors in localization of the HER2 and CEN-17 reactions. For this purpose, a thresholding based segmentation was investigated and its results were compared with segmentation based on the unsupervised neural network. Application of neural networks for segmentation was widely studied in literature [START_REF] Duraisamy | Cellular neural network based medical image segmentation using artificial bee colony algorithm[END_REF][START_REF] Long | Fully convolutional networks for semantic segmentation[END_REF]. Substantial portion of the reports deals with segmentations based on self-organized maps (SOMs). Yao et al. [START_REF] Yao | Unsupervised segmentation using a self-organizing map and a noise model estimation in sonar imagery[END_REF] have successfully applied SOMs to segment sonar images where each pixel of the input image is classified with the proposed neural network. Gorjizadeh et al. [START_REF] Gorjizadeh | Noisy image segmentation using a selforganized map network[END_REF] used a similar idea for segmentation of noisy medical images.

In 2001, Lerner et al. [START_REF] Lerner | Automatic signal classification in fluorescence in situ hybridization images[END_REF] described a neural network approach for detection of fluorescence in situ hybridization images. Their method is based on classification between a pair of in-and out-of-focus images. They use the in-focus images for further estimation of the FISH reactions. Results presented by the authors show an accuracy of 83-87%. Another approach, reported by Kiszler et al. [START_REF] Kiszler | Semi-automatic fish quantification on digital slides[END_REF], describes a semi-automated procedure applied to fluorescence in situ hybridization images. This procedure is based on the adaptive thresholding and the final counting is based on the selected areas of the image.

It can be easily noticed that Machine Learning is a popular tool for developing support software for supporting a diagnosis process of specialists. This is why as a main contribution of this paper we propose a fully automatic procedure for segmentation of HER2 and CEN-17 reactions that can be further counted to estimate the final FISH diagnosis. The final decision is based on the ASCO/CAP recommendations [START_REF] Ji | Clinicopathological variables predicting her-2 gene status in immunohistochemistry-equivocal (2+) invasive breast cancer[END_REF] that give a full route for HER2 testing in breast cancer.

Dataset

For the purpose of this study we have collected a database of 80 fluorescence in situ hybridization images with a size of 1376x1032 pixels recorded with a resolution of 200 pixels per inch. Example of the images in the database is shown in Fig. 2. Based on these examples it is easy to notice how difficult the automated segmentation of such images is. Images were recorder with an Olympus BX61 fluorescence microscope with X-Cite series 120Q EXFO fluorescent system. The microscope was equipped with a CCD Olympus XC10 camera working with a Cell-F visualization software. To capture the image it was required to use fluorescent filter such as 30-151332G-Ov2C146747 filter made by Abbott with a magnification of 60x and 100x. The database is a courtesy of dr. Anna Lis-Nawara and prof. Micha l Jeleń, the head of the Department of Pathology and Oncological Cytology at the Wroclaw Medical University, Wroc law, Poland.

HER2 and Cen-17 Segmentation

In computer vision, segmentation is a very crucial step that influences all subsequent phases of the classification systems. In medical image processing, the segmentation stage is always a very difficult task and that makes it a very active field of research [START_REF] Jeleń | Influence of Pattern Recognition Techniques on Breast Cytology Grading[END_REF][START_REF] Kowal | Computeraided diagnosis of breast cancer based on fine needle biopsy microscopic images[END_REF][START_REF] Lezoray | Segmentation of cytological images using color and mathematical morphology[END_REF]. In this research, we investigated two segmentation methods that will allow for the proposition of the automated segmentation framework for fluorescence in situ hybridization images. The first method is a simple thresholding were the threshold is automatically selected. The second method is an unsupervised neural network method where we made use of the self-organizing maps for segmentation of the receptors.

Simple Thresholding

To provide automatization of the segmentation procedure we decided to investigate one of the simplest automatic thresholding techniques proposed by Ridler and Calvard [START_REF] Ridler | Picture thresholding using an iterative selection[END_REF]. This method is based on a bimodal histogram of image gray levels. A threshold T is sought on the histogram curve according to equation 1.

T = µ 1 + µ 2 2 , (1)
where µ 1 and µ 2 are the means of the components separated by T . These means are calculated iteratively starting form the initial threshold that is typically set to an average gray level of the image. As mentioned before, HER2 reactions are visible as red dots and CEN-17 reactions are detectable as green dots. If we convert an RGB image to grayscale we would loose that information and therefore we need to apply the above mentioned segmentation to a color image. This means dividing the image into three separate planes (R, G and B). Each plane will represent the main color in the RGB color space. Looking at the nature of the images we can notice that the HER2 reactions are emphasized in a red channel and the CEN-17 reactions are affirmed in the green plane (see Fig. 3). We can take that information into consideration and apply Ridler and Calvard method to red and green image channels. Results of the application of this simple automatic thresholding method are presented in section 4.1.

Segmentation with Self Organizing Maps

As mentioned in section 1 self-organized maps (SOMs) can be successfully applied for a segmentation task. They reduce the input space into representative features according to a self-organizing process and are trained in an unsupervised manner [START_REF] Kohonen | The self-organizing map[END_REF]. These networks consist of only one layer with a linear transfer function for its neurons. It uses a comprehensive learning algorithm for weights estimation that updates the weight of only one, winning neuron for each input pattern. According to Kohonen [START_REF] Kohonen | The self-organizing map[END_REF] the introduction of an additional weight change of the neighboring neurons with smaller step size results in better correspondence to the features of the input data.

To train the SOM network we start with initialization of weights (w) with small random values and for each input data a winning neuron ( -→ i (x)) is found according to equation 2. Neighboring weights (w j (n + 1)) are then calculated according to equation 3.

- → i (x) = arg min j - → x (n) -w j , (2)
where -→ x (n) is an input vector.

w j (n + 1) = w j (n) + η(n)[x(n) -w j (n)] (3)
where η(n) is a neighboring function.

According to Kohonen, the neighborhood taken into consideration should be Gaussian and he suggests the neighborhood description according to equation 4.

Λ j,j o (n) = exp - |r j -r j o | 2 2σ 2 (n) (4)
where j o is the winning neuron and |r j -r j o | is a distance between the winning node and the j -th node, and σ 2 is a Gaussian variance. From this we can notice that this is an adaptive procedure, because the neighborhood and learning rate depend on the current iteration. Due to this fact our neighborhood should be as large as the output space at the start and should be decreasing during the iterations according to the equation 5. We can take the same reasoning for the step size, which should be big at the beginning and progressively decrease according to equation 6 until it reaches zero.

σ(n) = 1 c σ + d σ n (5) η(n) = 1 a η + b η n (6)
where a η , b η , c σ and d σ are constants.

Here we have adopted the SOM methodology to solve a segmentation problem for detection of HER2 and CEN-17 reactions in fluorescence in situ hybridization images. This task is divided into several stages. At first, we extract the red and green components from the RGB image, because these two channels provided the best localization of the reactions. Then we have applied a morphological reconstruction on both channels to extract the candidates of the red and green dots that represent HER2 and CEN-17 reactions respectively. These are actually the image maxima. Determination of these maxima can provide many misleading results such as multiple one-pixel dots. Some of these would also include background noise and for that reason there is a need to flatten them with reconstruction. This method is actually a morphological erosion and dilation followed by the reconstruction procedure according to the description of Luc Vincent [START_REF] Vincent | Morphological grayscale reconstruction in image analysis: Applications and efficient algorithms[END_REF].

According to Vincent, for an image I, called a mask, a reconstructed image (I r ) for a given marker M is calculated as a union of the connected components if the image which contain at least one mask pixel (see eq. 7).

I r = M ∩I k =0 I k (7)
To localize candidates for HER2 and CEN-17 indicators we first apply erosion and dilation to appropriate image channels and then we apply a reconstruction algorithm described above. A dilated image was used as a marker and eroded image was treated as a mask (see Fig. 5). As a result a flatten maxima area is obtained.

Knowing the exact location of each of the maxima we have to check if the area it represents is actually red. For this purpose, an color image is divided into areas equivalent to a bounding boxes of the image containing the maxima. All of these areas serve as a feature vector presented as an input to the neural network. If we take an area of 5x5px the obtained feature vector will contain 75 input weights. Such a large number of features suggests a high correlation between the features and therefore a dimension reduction is justified.

To remove redundancy and to reduce a feature vector length, all data was analyzed with principal component analysis (PCA) [START_REF] Jolliffe | Principal Component Analysis[END_REF] that used the singular value decomposition to determine the coefficients. Application of the PCA allowed for the reduction of the feature vector down to 3 independent components that characterize the variance changes in 97%. Such a feature vector is then presented as an input to the neural network which finds the areas concentrated around these tree groups. Analysis of obtained clusters determines the appropriate dots. Results of SOM segmentation are presented in section 4.1.

Experimental investigations

As mentioned in the previous section, to propose an automatic segmentation framework we need to concentrate on counting the visible HER2 and CEN-17 reactions. We propose to convert a color image into three components (red, green, blue) and search for the maxima on the red and green images. By applying the simple thresholding method to these channels we were able to obtain most of the reactions with a threshold value automatically selected for each image.

Unfortunately, this might lead to some problems in situations where some colors can contain higher values of red component that the red color itself. For that reason we split the procedure into two phases. In the first phase the algorithm looks for a red image maxima which serve as red dot indicators. In the next step we classify these indicators with a SOM network to determine which of them represent red dots. We can apply the same procedure for localizing green dots. When all reactions are detected it possible to calculate the a so called FISH coefficient that will be used for further diagnosis. Such a calculation is based on the ASCO/CAP [START_REF] Ji | Clinicopathological variables predicting her-2 gene status in immunohistochemistry-equivocal (2+) invasive breast cancer[END_REF] recommendation where a HER2 to CEN-17 ratio is calculated. Using this value we can further decide if the diagnosed case is FISH positive or negative. The main aim of this experimental work was to check the effectiveness of the SOM based segmentation approach applied to the database of the fluorescence in situ hybridization images in order to propose an automatic diagnosis system.

Results and Discussion

In this section, results of the automatic segmentation techniques described in section 3 are presented. In figure 4 we present an example of the segmentation obtained with simple automatic thresholding. From the example we can see that most of the reactions were localized and could be used for further FISH diagnosis calculations. It is easy to notice that after all, it will lead to some inaccuracies, especially in the red channel. The reason for that is that some of the nuclei assume some shades of red which will be misinterpreted with such a simple thresholding calculation. This will basically mean that the modes of the red channel histogram are not well separated. This scenario is better visualized in Fig. 7a. Taking the above into consideration we noted that application of the global thresholding will lead to misinterpretations due the fact that there are diverse intensity values in different parts of the image. This is why we decided to flatten the image maxima. This will allow us to use larger maxima areas instead of single peaks. For this purpose we decided to apply erosion and dylation operation followed by reconstruction according to the description in section 3.2. Results of the reconstruction are presented in Fig. 5.

From the results we can notice the detection of multiple one-pixel dots can provide many misleading results. This is because some of them will also include background noise, what could be noticed in case of simple thresholding.

Having the maxima determined and localized we can now check if the areas that are around the maxima contain red or green dot. As already described we proceed with division of the color image into sub-images that contain the maxima and treat it as a feature vector for SOM network. After dimension reduction we classify each of the extracted areas as a background or a red/green dot. A result of this operation is presented in Fig. 6. On the figure we can notice a good discrimination between background and dots. This is represented as a marker of a localization result. The presented segmentation results show that the SOM neural networks were able to properly distinguish HER2 and CEN-17 receptors. The main problem of this method occurs in a situation shown on Fig. 7b. Here a localization of green dots can be problematic but, in comparison with simple thresholding, we can still notice much better localization, especially in a red component. To complete the full automatic diagnosis, a number of red and green dots was calculated and HER2 to CEN-17 ratio was calculated. Based on the calculated ratio and according to ACSO regulations a FISH score was evaluated. For the simple thresholding 44 out of 80 images provided similar results as an expert pathologist diagnosis. The other method provided better results were 61 images had similar responds.

Conclusions and Future Work

In this study a problem of automatic segmentation of HER2 and CEN-17 reactions from Fluorescence in Situ Hybridization images was addressed. We have proposed a fully automatic segmentation framework that is able to detect dots representing reactions of human epidermal growth factor receptor 2 and chromosome 17 centromere enumeration probe with high precision. Form the results we can draw a conclusion that neural network based method is able to segment these reactions more accurate than the described simple thresholding method. As already mentioned this is caused by multiple one-pixel dots which eliminates a possibility of application of a global thresholding methods. It was shown that utilization of a reconstruction methodology along with morphological erosion and dylation allows for a better localization of the reactions. Although the results presented here are optimistic there are a few problems that can impair the overall diagnosis. The main issue is a localization of the dots in areas where they are not visible, as shown in Fig. 7. Another problem that can be distinguished here is segmentation of large number of dots as one large single dot. This can lead to incorrect interpretation of the result as several dots are counted as one.

One of the possibilities to improve the accuracy of the diagnosis would be an application of deep and convolutional neural networks which are showing to be very effective in cancer diagnosis. The main problem with these methods is necessity of a large number of training samples. This might be difficult to achieve as not all of the cases are stored digitally. This and other issues that are addressed here will be further researched as a future work.

Fig. 1 .

 1 Fig. 1. HER2 slides. a) ImmunoHistoChemistry staining image, b) FISH test image.

Fig. 2 .

 2 Fig. 2. Example of images in the database.

Fig. 3 .

 3 Fig. 3. FISH image RGB channels. a) Original image, b)Red channel, c)Green channel, d)Blue channel.

Fig. 4 .

 4 Fig. 4. Results of simple thresholding.

Fig. 5 .Fig. 6 .Fig. 7 .

 567 Fig. 5. Results of morphological reconstruction. a) Red channel, b) Green channel.


Robert Burduk
email: robert.burduk@pwr.edu.pl

Paulina Baczyńska
email: paulina.baczynska@pwr.edu.pl

Ensemble of Classifiers with Modification of Confidence Values

Keywords: Multiple classifier system, Decision profile, Confidence value

In the classification task, the ensemble of classifiers have attracted more and more attention in pattern recognition communities. Generally, ensemble methods have the potential to significantly improve the prediction base classifier which are included in the team. In this paper, we propose the algorithm which modifies the confidence values. This values are obtained as an outputs of the base classifiers. The experiment results based on thirteen data sets show that the proposed method is a promising method for the development of multiple classifiers systems. We compared the proposed method with other known ensemble of classifiers and with all base classifiers.

Introduction

For several years, in the field of supervised learning a number of base classifiers have been used in order to solve one classification task. The use of the multiple base classifier for a decision problem is known as an ensemble of classifiers (EoC) or as multiple classifiers systems (MCSs) [START_REF] Giacinto | An approach to the automatic design of multiple classifier systems[END_REF], [START_REF] Korytkowski | From ensemble of fuzzy classifiers to single fuzzy rule base classifier[END_REF]. The building of MCSs consists of three main phases: generation, selection and integration (fusion) [START_REF] Britto | Dynamic selection of classifiers-a comprehensive review[END_REF]. When injecting randomness into the learning algorithm or manipulating the training objects is done [START_REF] Breiman | Randomizing outputs to increase prediction accuracy[END_REF], [START_REF] Freund | Experiments with a new boosting algorithm[END_REF], then we are talking about homogeneous classifiers. In the second approach the ensemble is composed of heterogeneous classifiers. It means, that some different learning algorithms are applied to the same data set.

The selection phase is related to the choice of a set of classifiers from the whole available pool of base classifiers [START_REF] Jackowski | Improved adaptive splitting and selection: The hybrid training method of a classifier based on a feature space partitioning[END_REF]. Formally, if we choose one classifier then it is called the classifier selection. But if we choose a subset of base classifiers from the pool then it is called the ensemble selection or ensemble pruning. Generally, in the ensemble selection, there are two approaches: the static ensemble selection and the dynamic ensemble selection [START_REF] Baczyńska | Ensemble selection based on discriminant functions in binary classification task[END_REF], [START_REF] Britto | Dynamic selection of classifiers-a comprehensive review[END_REF].

A number of articles [START_REF] Duin | The combining classifier: to train or not to train? In Pattern Recognition[END_REF], [START_REF] Kuncheva | Combining Pattern Classifiers: Methods and Algorithms[END_REF], [START_REF] Xu | Methods of combining multiple classifiers and their applications to handwriting recognition[END_REF] present a large number of fusion methods. For example, in the third phase the simple majority voting scheme [START_REF] Ruta | Classifier selection for majority voting[END_REF] is most popular. Generally, the final decision which is made in the third phase uses the prediction of the base classifiers and it is popular for its ability to fuse together multiple classification outputs for the better accuracy of classification. The fusion methods can be divided into selection-based, fusion-based and hybrid ones according to their functioning [START_REF] Canuto | Investigating the influence of the choice of the ensemble members in accuracy and diversity of selection-based and fusion-based methods for ensembles[END_REF]. The fusion strategies can be also divided into fixed and trainable ones [START_REF] Duin | The combining classifier: to train or not to train? In Pattern Recognition[END_REF]. Another division distinguishes class-conscious and class-indifferent integration methods [START_REF] Kuncheva | Combining Pattern Classifiers: Methods and Algorithms[END_REF].

In this work we will consider the modification confidence values method. The proposed method is based on information from decision profiles. The decision scheme used in training phase is created only from these confidence values that concern to the correct classification.

The remainder of this paper is organized as follows. Section 2 presents the concept of the base classifier and ensemble of classifiers. Section 3 contains the proposed modification confidence values method. The experimental evaluation, discussion and conclusions from the experiments are presented in Section 4. The paper is concluded by a final discussion.

2 Supervised classification

Base classifiers

The aim of the supervised classification is to assign an object to a specific class label. The object is represented by a set of d features, or attributes, viewed as d-dimensional feature vector x. The recognition algorithm maps the feature space x to the set of class labels Ω according to the general formula:

Ψ : X → Ω. (1)
The recognition algorithm defines the classifier, which in the complex classification task with multiple classifiers is called a base classifier.

The output of a base classifier can be divided into three types [START_REF] Kuncheva | Combining Pattern Classifiers: Methods and Algorithms[END_REF].

-The abstract level -the classifier ψ assigns the unique label j to a given input x. -The rank level -in this case for each input (object) x, each classifier produces an integer rank array. Each element within this array corresponds to one of the defined class labels. The array is usually sorted and the label at the top being the first choice. -The measurement level -the output of a classifier is represented by a confidence value (CV) that addresses the degree of assigning the class label to the given input x. An example of such a representation of the output is a posteriori probability returned by Bayes classifier. Generally, this level can provide richer information than the abstract and rank level.

In this work we consider the situation when each base classifier returns CVs. Additionally, before the final combination of base classifiers' outputs the CVs modification process is carried out.

Ensemble of classifiers

Let us assume that k ∈ {1, 2, ..., K} different classifiers Ψ 1 , Ψ 2 , . . . , Ψ K are available to solve the classification task. The output information from all K component classifiers is applied to make the ultimate decision of MCSs. This decision is made based on the predictions of all the base classifiers. One of the possible methods for integrating the output of the base classifier is the sum rule. In this method the score of MCSs is based on the application of the following sums:

s ω (x) = K k=1 p k (ω|x), ω ∈ Ω, (2)
where p k (ω|x) is CV for class label ω returned by classifier k.

The final decision of MCSs is made following the maximum rule:

Ψ S (x) = arg max ω s ω (x). (3)
In the presented method (3) CV obtained from the individual classifiers take an equal part in building MCSs. This is the simplest situation in which we do not need additional information on the testing process of the base classifiers except for the models of these classifiers. One of the possible methods in which weights of the base classifier are used is presented in [START_REF] Burduk | Classifier fusion with interval-valued weights[END_REF]. Decision template (DT) is another approaches to build the MCSs. DT was proposed in [START_REF] Kuncheva | Decision templates for multiple classifier fusion: an experimental comparison[END_REF]. In this MCS model DTs are calculated based on training set. One DT per class label. In the operation phase the similarity between each DT and outputs of base classifiers for object x is computed. The class label with the closest DT is assigned to object x. In this paper algorithm with DT is labelled Ψ DT and it is used as one of the reference classifiers.

Modification of confidence values algorithm

Training phase

[16] The proposed algorithm of the modification CVs values uses DPs. DP is a matrix containing CVs for each base classifier, i.e.:

DP (x) =    p 1 (0|x) . . . p 1 (Ω|x) . . . . . . . . . p K (0|x) . . . p K (Ω|x)    . (4)
In the first step of the algorithm we remove CVs which relate to the misclassification on the training set. This set contains N labelled examples {(x 1 , ω 1 ), ..., (x N , ω N )}, where ω i is the true class label of the object described by feature vector x i . CVs are removed according to the formula:

p k (ω|x) = p k (ω|x), if I(Ψ (x), ω) = 1 0, if I(Ψ (x), ω) = 0. ( 5
)
where I(Ψ (x), ω) is an indicator function having the value 1 in the case of the correct classification of the object described by feature vector x, i.e. when Ψ (x) = ω.

In the next step, our algorithm, the decision scheme (DS) is calculated according to the formula:

DS(β) =    ds(β) 10 . . . ds(β) 1Ω . . . . . . . . . ds(β) K0 . . . ds(β) KΩ    , (6)
where

ds(β) kω = ds kω + β N n=1 (p k (ω n |x n ) -ds kω ) 2 N -1 (7)
and

ds kω = N n=1 p k (ω n |x n ) N . ( 8
)
The parameter β in our algorithm determines how we compute DS elements. For example, if β = 0, then ds kω is the average of appropriate DFs received after the condition (5).

Operation phase

During the operation phase the modification of CVs is carried out using DS(β) calculated in the training phase. For the new object x being recognized, the outputs of the base classifiers construct DP (x) as in ( 4). The modification CVs from DP (x) is performed with the use of DS(β) calculated in [START_REF] Canuto | Investigating the influence of the choice of the ensemble members in accuracy and diversity of selection-based and fusion-based methods for ensembles[END_REF] according to the formula:

p k (ω|x) =    m * p k (ω|x) if p k (ω|x) ≥ ds(1) kω m * p k (ω|x) if ds(0) kω < p k (ω|x) < ds(1) kω , m * p k (ω|x) if p k (ω|x) ≤ ds(0) kω (9)
where m, m and m define how ordinal CVs are modified. The modification process taking into account the equation ( 9) causes the ensemble of the classifier method to use the modified CVs. The algorithm using the proposed method is denoted as Ψ M CV . In the experiment modified CVs are combined according to the sum method (3).

Experimental studies

In the experiments we use 13 data sets. Nine of them come from the Keel Project [START_REF] Alcalá | Keel data-mining software tool: Data set repository, integration of algorithms and experimental analysis framework[END_REF] and four com from UCI Repository The main aim of the experiments was to compare the quality of classifications of the proposed modification CVs algorithms Ψ M CV with the base classifiers Ψ 1 , ..., Ψ 16 and their ensemble without the selection Ψ DT and Ψ S . The parameters of Ψ M CV algorithm were established on m = 1.25, m = 1 and m = 0.75. In the experiments the feature selection process [START_REF] Inbarani | Supervised hybrid feature selection based on pso and rough sets for medical diagnosis[END_REF], [START_REF] Rejer | Genetic algorithm with aggressive mutation for feature selection in bci feature space[END_REF] was not performed and we have used the standard 10-fold-cross-validation method. The classification error with the mean ranks obtained by the Friedman test for classification algorithms used in the experiments are presented in Tab. 2. Considering only the mean ranks obtained by the Friedman test the best result achieved proposed in the work algorithm labelled Ψ M CV . The obtained results were compared also by the post-hoc test [START_REF] Trawiński | Nonparametric statistical analysis for multiple comparison of machine learning regression algorithms[END_REF]. The critical difference (CD) for this test at p = 0.05 is equal to CD = 7.76 -for 19 methods used for classification and 13 data sets. We can conclude that the post-hoc Nemenyi test detects significant differences between the proposed algorithm Ψ M CV and the four base classifiers Ψ 4 , Ψ 6 , Ψ 8 , and Ψ 14 . The classifier method labelled Ψ S is statistically better than the three base classifiers Ψ 6 , Ψ 8 and Ψ 14 . This confirms that the proposed algorithm is better than the ensemble of classifiers with the used sum method. It should be noted, however, that the difference in average ranks is not large enough to point to the significant differences between Ψ M CV and Ψ S algorithms.

[ 9 ]

 9 (Blood, Breast Cancer Wisconsin, Indian Liver Patient and Mammographic Mass UCI). The details of the data sets are included in Tab. 1. In the experiment 16 base classifiers were used from four different classification models. The first group of four base classifiers works according to k -N N rule, the second group uses the Support Vector Machines models. The next group uses the Neural Network model and the last group uses the decision trees algorithms. The base classifiers are labelled as Ψ 1 , ..., Ψ 16 .

Table 1 .

 1 Description of data sets selected for the experiments

	Data set	example attribute ration (0/1)
	Cylinder Bands	365	19	1.7
	Haberman's Survival	306	3	2.8
	Hepatitis	80	19	0.2
	Mammographic Mass	830	5	1.1
	Parkinson	197	23	0.3
	Pima Indians Diabetes	768	8	1.9
	South African Hearth	462	9	1.9
	Spectf Heart	267	44	0.3
	Statlog (Heart)	270	13	1.3
	Blood	748	5	3.2
	Breast Cancer Wisconsin	699	10	1.9
	Indian Liver Patient	583	10	0.4
	Mammographic Mass UCI 961	6	1.2

Acknowledgments. This work was supported by the Polish National Science Center under the grant no. DEC-2013/09/B/ST6/02264 and by the statutory funds of the Department of Systems and Computer Networks, Wroclaw University of Technology.

Conclusion

In this paper we have proposed the methods that use information from the decision profiles and modified CVs received from the base classifiers. The aim of the experiments was to compare the proposed algorithm with all base classifiers and the ensemble classifiers based on the sum and decision profile methods. The experiments have been carried out on 13 benchmark data sets. We can conclude that the post-hoc Nemenyi test detects significant differences between the proposed algorithm Ψ M CV and four base classifiers. While the algorithm Ψ S classification results are statistically different from the three base classifiers. The obtained results show an improvement in the quality of the classification proposed algorithm Ψ M CV with respect to all the base classifiers and the used reference ensemble of the classifiers' methods. Future work might involve the application of the proposed methods for various practical tasks [START_REF] Forczmański | Recognition of occluded faces based on multisubspace classification[END_REF], [START_REF] Frejlichowski | An algorithm for the automatic analysis of characters located on car license plates[END_REF], [START_REF] Zdunek | Statistical classification of soft solder alloys by laser-induced breakdown spectroscopy: review of methods[END_REF] in which base classifiers are used. Additionally, the advantage of the proposed algorithm can be investigated as well as its ability to work in the parallel and distributed environment.


Janusz Rafałko

Algorithm of allophone borders correction in automatic segmentation of acoustic units

Keywords: Speech, speech synthesis, allophone, phoneme, text to speech, tts, acoustic units, speech processing, border correction

In concatenative speech synthesis the fundamental factor with heavy influence on synthesized speech quality is the database of acoustic units. In case of bases received in automatic way, the key matter is suitable marking the borders of acoustic units. This article describes the algorithm of correction of acoustic units borders appointive in automatic way. It is based on two factors specified and tested here. It also describes worked out method of grade of acoustic units database, which allows to observe the influence of introduced correction on the base quality.

Introduction

The main goal in speech technology is to create a speech which is almost as real as a voice of a living person. One of the methods of speech synthesis based on the text (Text to Speech), which allows to reproduce the human personal speech characteristics is a concatenation method. It uses small and natural acoustic units, from which the speech is synthesized. These can be allophones, diphones or syllables. In presented system, synthesizer is based on bases composed of allophones. That type of system synthesizes the speech by joining the acoustic units in accordance to appropriate phonetic rules. The individual features of human voice are not included in this rules, but only in natural acoustic units. In order to synthesize the voice of a particular man, an acoustic units database must be created.

The acoustic units databases are the allophones bases. Preparing such base takes months and it is done by experts in a manual way. Therefore there is a demand to work out an automatic method of creating such bases e.g. presented in [START_REF] Almpanidis | Automatic Phonemic Segmentation Using The Bayesian Information Criterion With Generalised Gamma Priors[END_REF][START_REF] Szklanny | Creation and analysis of a Polish speech database for use in unit selection speech synthesis[END_REF]. As a result of working the system in automatic way, the borders of allophones are marked.

In order to obtain the best quality of synthesized speech, the borders have to be marked in a precise way. Introduced in this paper algorithms allow to correct errors of marking these borders.

Acoustic units database

Different approaches to the speech synthesis from the text are described in [START_REF] Dutoit | An Introduction to text-to-speech synthesis[END_REF][START_REF] Taylor | Text-to-Speech Synthesis[END_REF]. The basic feature of concatenative approach of speech synthesis is the use of elementary pieces of natural speech [START_REF] Van Santen | Progress in speech synthesis[END_REF]. In the synthesizer, the signal compiled from natural speech segments is a subject of further modification which changes the prosodic parameters of the signal.

In the [START_REF] Szpilewski | Polish TTS in Multi-Voice Slavonic Languages Speech Synthesis System[END_REF], study shows the basic assumptions of concatenative TTS system for Polish language, based on allophones in the context of multilingual synthesis. Natural elements from which the speech is synthesized may be allophones, diphones, multiphones as well as syllables. In concatenative method of speech synthesizing these type of basic speech units has much influence on obtaining individual speech characteristics. This paper refers to the databases of acoustic units, which include several context groups of particular phoneme, which may be identified with acoustic allophone, described in the study of Jassem [START_REF] Jassem | Podstawy fonetyki akustycznej[END_REF]. The advantages of the choice of allophones as a basic units [START_REF] Lobanov | Реализация межъязыковых различий интонации завиершённости и незавиершённости в синтезаторе русской и полской речи по тексту[END_REF][START_REF] Matoušek | Building a New Czech Text-to-Speech System Using Triphonebased Speech Units[END_REF][START_REF] Rafalko | The algorithms of automation of the process of creating acoustic units databases in the Polish speech synthesis[END_REF][START_REF] Skrelin | Allophone-based concatenative speech synthesis system for Russian[END_REF] base on the fact that firstly -speech units remain the effects of sounds interference, and secondly -the number of basic units is relatively low and holds in the range of 400 -2000 in different systems. The difficulty posing in this approach is a necessity of precise allophones marking during the segmentation of natural speech signal.

Automatic segmentation of natural speech signal

If in the speech synthesis the compilation elements contain only the phonetical and acoustical characteristics, the segmentation task is about to "cut" the basic segments from the speech stream and place them into the database. The main stages of this algorithms include:

1. Selection and preparation of text and acoustic corpuses.

2. The automation of creation of acoustic units databases of the particular speaker voice.

As a result of this work system, we get many of the same units, but we need only one piece of each element to our base. In order to create an acoustic database it is necessary to analyze received units in details and delete those phonetic units in which the acceptable error during reading or automatic segmentation was exceeded and save only the best of them. If there are more than one identical allophones, we choose the best one. Finally we must perform the control of quality of each element that left, marking deviations and perform the correction of segments parameters with noticed deviations.

Correction algorithm

The "correction" operation is performed for those segments, which are obtained in accordance to the ways mentioned above. The segments with inaccurately defined limits are subject to correction using proper procedures, involving removing the inaccurate periods of basic tone and inserting the missing terminal periods of basic tone. The diagnosis of determining the limits of units is performed by determining the level of time between periods and acoustic signal characteristics similarities on the first and the second period of basic tone, as well as on the penultimate and the last one. Both cases of periods: first, second and penultimate, the last, will be described as terminal and pre-terminal. The correction is performed only in the case of voiced units.

To determine the level of similarity of terminal and pre-terminal period of acoustic characteristics, the formula 1a) is used. The distance between time characteristics is calculated as a ratio of duration of these periods (formula 1b).

a),

          N i P i G i N i P i G i A s s s s L 1 1 1 b),     P G P G T T T T T L , max , min 1   (1)
where:

s i
Gvalue of the signal at the "i" segment of terminal period s i Pvalue of the signal at the "i" segment of pre-terminal period T G , T Pduration of periods, both the terminal and the pre-terminal These factors assume value of range 0 -1. The factor of the time adjustment L T is constructed in such a way, that it takes low value for similar duration of terminal and pre-terminal period of acoustic unit, achieving value 0 when these periods are identical. When the durations differ from each other, this factor grows up to value 1. On the contrary factor L A vice versa, similar periods -value close to 1. "Correction" consists of removing terminal period and duplicating pre-terminal one. In result the number of periods of segment basic tone does not change. The second case of "correction" is an absolute rejection of terminal period. Whereas in case of the correct marking of border unit, such period remains. In order to find the appropriate values of the factors by which terminal period should be remove or improve by replacing them with pre-terminal, it was analyzed various bases received as a result of automatic segmentation. It was set experimentally, that when factor L T < 0,2 it means, that terminal and preterminal periods have similar durations and terminal period might be left without changes. Example of such situation is presented on fig. 1. If value of factor L T is between 0.2 and 0.7 terminal period should be replaced by preterminal. Example of such situation is presented on next fig. 2. We can notice here that border was marked in mid-period, therefore it should be replaced by pre-terminal period. Third case refers to factor L T > 0.7. It means that terminal period is too short. Fig. 3 shows that the border of unit is marked just behind the border of pre-terminal period. In such cases terminal period is removed. When L A is in range 0.4 < L A < 0.6 terminal period is replaced by pre-terminal period.

We can see it on fig. 4. The value L A = 0.57 means that period will be replaced by pre-terminal. We can see (fig. 4) that terminal period is different from other periods of allophone unit therefore it should be replaced. The first and the third cases are trivial. The replacement of terminal period by preterminal is a second case of correction. Fig. 6 presents the allophone before correction terminal period pre-terminal period terminal period pre-terminal period of primary border period and the same unit after correction. The correction coefficients of initial border periods of this element are L T = 0.3 and L A = 0.63. Fig. 6. Unit "a2020" before and after replacement terminal period by pre-terminal period.

The base correctness ratio

Taking into account parameters L T and L A it is possible to construct the ratio showing the correctness of cutting an acoustic unit, and after averaging -the ratio showing the correctness of whole base. Obviously, it will be showing only correctness of cutting voiced units. We can introduce the summary degree of similarity of terminal periods appointed as:

2 T A L L L   (2)
Factors L A and L T are constructed in such a way, that for correctly cut allophone L A the value will be close to 1, but L T close to 0. So total ratio for correctly cut segments should have the value approximate to 0.5. Upon introducing the average for this grade of similarity for all units in base we can receive the base correctness ratio:

    N i i T i A BCR L L N L 1 2 1 (3)
Fig. 7 presents the ratio L histogram of acoustic units of voice standard base prepared manually. The average value that is the ratio of correctness for this base is L BCR = 0,48. We can see that this ratio distribution is similar to Gaussian distribution. Next graphs show histograms of ratio L before correction (fig. 8) and after correction (fig. 9). It is a base obtained in automatic way, for the same voice that standard base. In this case the base correctness ratio is about L BCR = 0.51. There can be many reasons why the value of ratio L had deviated from 0.5 for the unit. The reason might be incorrectly marked borders of periods by implemented algorithm. However basic cause is the fact that terminal and pre-terminal periods in allophone need not and in practice cannot be identical.

Fig. 1 .

 1 Fig. 1. Terminal and pre-terminal periods of "wi03" unit, L T = 0.19.

Fig. 2 .

 2 Fig. 2. Terminal and pre-terminal periods of "a0130" unit, L T = 0.44.

Fig. 3 .

 3 Fig. 3. Terminal and pre-terminal periods of "e1001" unit, L T = 0.92.In case of factor L A we can also distinguish three cases. First of them, when L A is larger (L A > 0.6) means, that terminal and pre-terminal periods are similar in acoustic consideration to each other. In such case operation depends on ad valorem factor L T . Examples are presented on previous fig.3illustrates case, when L A = 0.89 but never-

Fig. 4 .

 4 Fig. 4. Terminal and pre-terminal periods of "n03" unit, L A = 0.57. If L A < 0.4 terminal period should be removed without any regard to value of factor L T . Example is presented on next fig. 5. We can see that the algorithm of border marking is marked incorrectly in the last period.

Fig. 5 .

 5 Fig. 5. Terminal and pre-terminal periods of "l02" unit, L A = 0.06. The analysis of all those cases for various bases led to defining required values of these factors and to determining when and how an allophone is a subject to a correction. If:  L T < 0.2 and L A > 0.6terminal period remains firm;  0.2 < L T < 0.7 and L A > 0.4terminal period is replaced by pre-terminal;  L T > 0.7 or L A < 0.4terminal period is removed;

Fig. 7 .

 7 Fig. 7. Histogram of the factor L of the standard base.

Fig. 8 .

 8 Fig. 8. Histogram of the factor L of automatic base before borders correction.

Fig. 9 .

 9 Fig. 9. Histogram of the factor L of automatic base after borders correction.

L

Summary

Research shows, that presented correction algorithms of borders of allophones appointed in automatic way improve the quality obtained base. Feedback from subjective researches also confirms it. It turns out that analytic base correctness ratio is a useful tool which, in numerical way, defines the quality of allophonic bases. Drawback of this approach and simultaneously drawback of this ratio, is the fact that it is possible to apply it only to voiced units of speech signal. However theoretically it is possible to use it in order to describe the quality of bases composed of other acoustic units than allophones.

7

Bibliography


W Ladys Law Homenda

Krystian Kwieciński

Attribute Grammars for Controlling House Layout Customization

Keywords: syntactic methods, context-free grammars, attribute grammars, design automation, house layout

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

One reason for which design automation is of significant research interest is that it provides a basic reference for comparing different processing technologies. However, a more fundamental reason is that it focuses on the essence of intelligent information processing, the formation of abstractions. This paper provides a valuable insight into the methodologies that lead to comprehensive and interpretable results and that ensure the transparency of final findings. In one way or another there arises an issue of casting the results as information structuring conceptual entities that capture the essence of the overall data set in a compact manner. It is worth stressing that information structures not only support conversion of detailed data into more tangible information entities but, very importantly, afford a vehicle of abstraction that allows to think of structures as different conceptual structures. A context-free grammars were chosen due to its simplicity and possibility of augmenting them with the mechanism of attributes propagation. Clearly the task of information structuring is not a trivial one and it is dependent to a large extent on the application domain. Let us discuss the overall perspective on house layout design automation. Assuming that X is a set of basic design entities (living room, bedroom, kitchen etc.), we may express all possible arrangements of them as a power set (with repetitions of entities) P(X), as illustrated in Figure 1. We build a context-free grammar to generate arrangements of entities of X. Of course, only a small proportion of elements of P(X) represent arrangements, which conform to the rules of such a grammar. These represent a subset of P(X), referred to as G(X). And the grammatically correct arrangements that are meaningful are represented by S(X) that is a subset of G(X). The entities (X) themselves have a dual nature; on one hand they have grammatical meaning (parts of arrangements) and on the other hand they have semantics defined by the concepts they represent (function, size, neighborhood etc.). The essence of syntactical analysis is to discriminate whether a given arrangement belongs to G(X) or P(X) -G(X). Syntactical analysis dissects the arrangements into higher level parts of a house (bay, private zone, semipublic zone etc.) and checks for conformity with the rules of grammar until the bottom-most level of individual entities is reached. A standard approach to syntactical analysis involves application of parsing techniques to check the conformity of a given arrangements with the rules of grammar. As adverted above, not all syntactic correct arrangements G(X) are meaningful, i.e. many of them do not conform to semantic constrains. Elimination of incorrect arrangements is accomplished with attributes, which furnish the context-free grammar. Attributes provide mechanisms of information flow in a derivation (parsing) tree of given arrangement and in this way allow to encounter semantic information in terms of supplementary rules and constrains verification. This study is motivated by fundamental ideas of syntactic methods employed to knowledge processing [START_REF] Bargiela | Information structuring in natural language communication: Syntactical approach[END_REF][START_REF] Higuera | A bibliographical study of grammatical inference[END_REF] and their application in different domains, for example: intelligent man-machine communication [START_REF] Homenda | Integrated syntactic and semantic data structuring as an abstraction of intelligent man-machine communication[END_REF][START_REF] Homenda | Automatic data understanding: a necessity of intelligent communication[END_REF], music information processing [START_REF] Homenda | Querying in Spaces of Music Information[END_REF] and human behavior [START_REF] Rosani | Human behavior recognition using a context-free grammar[END_REF].

The paper is structured as follows. Next subsections introduce the subject (the domain of house layout design) and the tool used (context-free and attribute grammars). In Section 2 syntactic structuring of the target objects is outlined with context-free grammars employed. Section 3 attributes supplementing context-free grammars are pursued to accomplish semantic information.

The Subject: House Layout Customization

Automatic generation of house layouts has been previously studied both for historical architectural styles [START_REF] Stiny | The palladian grammar[END_REF] as well as for the designs of contemporary living architects [START_REF] Duarte | Customizing mass housing: a discursive grammar for Siza's Malagueira houses[END_REF]. Previous researches utilized shape grammars in order to formalize architectural rules as a series of transformations of shapes.

An architectural design system proposed by Kwieciński [START_REF] Kwieciński | Interactive design system for provisioning of customized houses[END_REF], was intended to allow customers participation in the generation of customized houses. Proposed system, which consist of three modules: Site Planner, Home Planner and Facade Creator, was designed to produce single story or two story buildings, with a two bay house layouts and a gable roof. Home Planner, which is responsible for the generation and customization of house layout, collects architectural design principles responsible for the distribution of rooms into the bays on each floor. Spatial distribution of rooms takes place in relation to the external and internal context. For this purpose the orientation to the World coordinates (which affects indoor sunlight), orientation to the entrance to the plot and the privacy gradient (which suggests placing common areas, such as the living room, closer to the entrance, while private spaces, such as bedrooms farther away) are considered in the design system. Therefore the rooms are grouped into three zones: entrance zone, semipublic zone and private zone which constrain the freedom of layout configurations. Additionally some rooms are required to be placed next to each other like kitchen and dining room for example. Both of these rooms belong to semipublic zone together with living room, which is obligatory in every layout and home office which is optional and staircase which existence depends on the number of floors. If the house is not a single story building then localization of staircase is duplicated on the second floor and the generation of the first floor determines the generation of the second floor. When a planar layout of the spaces on each floor is completed it can be further customized by the user and further developed. Figure 2 presents exemplary two story building. Left side of the figure presents detailed floor plan with introduced walls and furniture and right side of the figure presents diagrammatic layout where rooms are represented by colored and named matrices of 60 by 60 cm modules. Building is having rectangular shape with only exception of garage which sticks out of the shape. Layout is divided in the middle into two part which represents different buildings bays. Bays are having same depth and equal length which is the same as the building length.

The Tool: Syntactic Structuring

Syntactic approach is a crucial stage and a crucial problem in the wide spectrum of tasks as, for instance, pattern recognition, translation of programming languages, processing of natural languages, music processing, etc., cf. [START_REF] Bargiela | Information structuring in natural language communication: Syntactical approach[END_REF][START_REF] Homenda | Integrated syntactic and semantic data structuring as an abstraction of intelligent man-machine communication[END_REF][START_REF] Homenda | Querying in Spaces of Music Information[END_REF]. By syntactic approach and syntactic methods we understand grammars, automata, algorithms used in processing languages. In this paper we employ context-free grammars to controlling house layout customization.

Context-free Syntactic Description

The discussion on describing and controlling house layout is based on common definitions of grammars, context-free grammars and attribute grammars. We assume that the reader is familiar with the basic notions of mathematical linguistic. Therefore, we only recall them.

Let us recall that a system G = (V, T, P, S) is a grammar, where: (a) V is a finite set of variables (called also nonterminals), (b) T is a finite set of terminal symbols (simply called terminals), (c) a nonterminal S is the initial symbol of the grammar and (d) P is a finite set of productions. A pair (α, β) of strings of nonterminals and terminals is a production assuming that the first element α of the pair is a nonempty string. Productions are usually denoted α → β. Grammars having all productions with α being a nonterminal symbols are context-free grammars.

A derivation in a grammar is a finite sequence of strings of nonterminals and terminals such that: (a) the first string in this sequence is just the initial symbol of the grammar and (b) for any two consecutive strings in the sequence, the later one is obtained from the former one applying a production in the usual way, i.e. by replacing a substring of the former string equal to the left hand side of the production with the right hand side of the production. We say that the last element of the string is derivable in the grammar.

For a context-free grammar a derivation can be outlined in a form of derivation tree, i.e. (a) the root of the tree is labelled with the initial symbol of the grammar and (b) for any internal vertex labelled by the left side of a production, its children are labelled by symbols of the right side of the production.

Attribute Grammars An attribute grammar is a formal way to define attributes for the productions of a formal grammar, cf. [START_REF] Knuth | The genesis of attribute grammars[END_REF]. The attributes are tied to symbols of productions (terminal and nonterminal symbols). The attributes are divided into two groups: synthesized attributes and inherited attributes. The attributes are assigned values at the derivation process. The values of the inherited attributes are passed down from parent nodes. The values of the synthesized attributes are the results of the attributes' evaluation rules applied to right hand side of the production or, for derivation tree, to children of a node. For simplification, the values of the synthesized attributes can be computed using inherited attributes and across from left neighbors.

In our approach, synthesized attributes are used to pass semantic information up the parse tree, while inherited attributes help pass semantic information down and across it. Attributes make it possible to validate semantic checks associated with a grammar, representing the rules of a language not explicitly imparted by the syntax definition. The strength of attribute grammars is that they can transport information from anywhere in the abstract syntax tree to anywhere else, in a controlled and formal way.

2 Syntactic Structuring -House Layout Customization

The Grammar

The initial productions of the grammar create the topmost level of hierarchy defining floors of the subjected house. Depending on the number of floors they are being placed in the Floor dimension. Floors of the house are having its length therefore they can also be placed in Length dimension. Building floors can be longitudinally divided into separate bays. If building is having rectangular shape then the floors are also rectangular and eventually bays are having equal length which is equal to the length of the building. Buildings might have various number of bays depending on its functional program, structural system and building typology. Therefore for the purpose of gable-front house presented grammar was simplified to the grammar generating just two bays of equal length on all the floors. <building> → <f loor> <buidling> → <f loor> <f loor> → <bay1> <bay2>

The fallowing part of the grammar divides Bays into zones. Zones allows to group rooms in order to prevent unallowable configurations of rooms. Rooms are grouped into three zones which correspond to degree of their privateness in the building. Lay out of zones create a sequence which begins with the entrance zone which is fallowed by semipublic zone and privet zone.

<bay1> → <zone entrance> <bay1>

→ <zone semipublic> <bay1> → <zone private> <bay1> → <zone semipublic> → <zone private> <bay2> → <zone entrance> <bay2>

→ <zone semipublic> <bay2> → <zone private> <bay2> → <zone semipublic> → <zone private>

The next part of the grammar generate rooms in the Length dimension inside entrance zone. Entrance zone is divided into entrance slot and technical slot. Slots are introduced to allow placing collection of rooms across bays. They allow to generate rooms in the same bay and at the same localization along Length dimension but one after the other. The placed rooms have the width of the slot (exception is garage which protrude rectangular building shape) and the sum of rooms depth is equal to the depth of the slot. It is also used to introduce hall in front of the room. <zone entrance> → <entrance slot> <technical slot> <entrance slot> → <vestibule> <garage> <vestibule> → vestibule <garage> → garage <technical slot> → <hall> <toilet> <tech room> <hall> → hall <toilet> → toilet <tech room> → tech room

The fallowing part of the grammar presents method for generating sequence of rooms inside semipublic zone. For the purpose of constraining generation of rooms in relation to each other s slot and s set which stands for semipublic slot and set were introduced. As it was described in the previous paragraph slot allows to place collection of rooms across bay at the same Length dimension. Therefore it was utilized to introduce hall in front of the room. Contrary set allows to force generation of certain rooms next to each other. In the presented grammar kitchen is always being placed next to the dining room. Moreover both of this rooms can either have or not have a hall attached to it. Therefore the set in this case is combined of the slots allowing to introduce hall. Presented method could be easily adopted for the purpose of privet zone therefore presentation of this part of grammar was omitted in this article. <zone semipublic> → <s slot> <zone semipublic> → <s set> <zone semipublic> → <s slot> → <s set> <s slot> → <hall> <s slot room> → <s slot room> <s slot room> → living room | home office | stairs <s set> → <s set slot> <s set slot> → <s set slot> <s set slot> → <hall> <s set slot room> → <s set slot room> <s set slot room> → kitchen | dining room

Derivation Trees

Derivation trees of language constructions in given grammar are best to identify syntactic structuring. Therefor, derivation tree of exemplary two story gablefront house, presented in Figure 2, is considerd. Figure 3 presents a part of a derivation tree of the house layout from Figure 2. The derivation tree covers second bay of the ground floor. The derivation is developed to the level of individual rooms area forming layout of the house.

Semantic Analysis -Design Control

To verify the design of the house layout the data regarding the total width of all the bays and the location, width, adjacency and accessibility of every room has to be verified. Therefore such data has to be provided in the grammar or -more precisely -in the derivation tree. To transfer needed data we can use attributive tools in the grammar, i.e. we use attributive grammars. Such grammar is obtained by furnishing productions with inherited and synthesized attributes.

Attributes are attached to the grammar considered in this paper. They are responsible for collecting and transferring important data between items of the information space. Complete grammar with all the attributes and rules of their evaluation is not being presented in this paper. Instead ideas of using attributes are being outlined.

Verification of room addition

In order to guarantee the completeness of building layout it has to be verified that all the required rooms were added. Figure 4 presents two methods for verifying this requirement. Left side of the figure presents an example of synthesizing the attributes of count s which calculates the total number of stairs added to the building layout. The data collected by this attribute is being verified at the trunk of the derivation tree in order to check if the total amount of stairs meets the required amount. Right side of the figure presents an example of inheriting attributes of count s. This attribute is also used to calculate the total number of stairs added to the building layout but the data collected by it is verified after any room is added to the layout. The second method allows to prevent invalid grammar productions before they are completed while the first one require to generate complete house layout which afterwards is being verified. Based on these methods the amount of all required rooms can be individually verified.

Verification of widths

Verification of room width in order to fit to the allowed range is a trivial task and is being checked at the level of individual rooms (leaves). Additionally verification of the length of all the bays on all the floors also has to be checked, in order to guarantee rectangular shape of the building. Figure 5 presents an example of inheriting attribute of the building width and synthesizing the attributes of rooms width. Attributes of given nonterminal and their values are listed below nonterminal's name. Arrows with attributes names show direction of flow of values of attributes. For instance, the nonterminal <bay2> has attribute: f ree width. This attribute get value from attributes of <zone entrance>: f ree width. Which in turn gets the value from synthesize attributes from generated elements of house layout slot width and slot width and inherit attribute from <bay2> f ree width.

The date collected at the nonterminal <zone semipublic> of the derivation tree allows to further calculate total free bay's width which is left to allocate next room before it is being added. If attribute f ree width is equal zero then no additional room can be added and the length of bays are equal and they are equal to the width of the building. If it is bigger then zero there is still left space to add another room. When it is lower then zero then the added room is too big and it's size has to be reduced or this room has to be removed. This verification allows to control that the house is in a rectangular shape.

Verification of zones connectivity

As it was described in Section 2 bays are being divided into zones, which group rooms in order to place them next to each other. Therefore different bays could be differently divided into zones. In order to provide continuity of zones in the building layout the connectivity of this zones laying in different bays has to be verified. Figure 6 presents an example of information flow in the derivation tree of an attributive grammar which allows to control connectivity of semipublic zones on the ground floor. For instance, the nonterminal < bay2 > has attributes: bay2 s start and bay2 s end which represents the beginning and the end localization of the semipublic zone placed in bay2. The attributes get the value of <zone semipublic>: start and zone width. The start value is being inherited from the nonterminal <zone entrance> zone width. The zone width gets the value from synthesize attributes from generated elements of house layout slot width and zone width. The date collected at the nonterminal <f loor> of the derivation tree allows to calculate if the semiprivate zones placed in different bays overlap for at least 2 modules which guarantees their connectivity. This method can also be utilized to control rooms adjacency. Division of bays into zones allow to control if the rooms are grouped correctly. Additionally sets of rooms allow to control if the required rooms are placed next to each other in the same bay. But these conditions are not enough to ensure that the required rooms are placed next to each other when they are added to the different bays. Therefore presented in a previous paragraph method allows also to control adjacency of rooms being placed in two different bays.

Conclusions

This paper introduces a new framework for design automation, which is a case of more general problem of building tools for operating on knowledge structures. The discussion is focused on syntactic processing nested in a selected architecture problem of house layout customization. House layout is interpreted as multi dimensional concepts structure of domain knowledge. Syntactic structuring is based on context-free methods. We propose constructions of context-free grammars driven by concepts of multidimensional knowledge space. The formalism affords consistent representation of an approximate grammatical correctness of house layout. Furnishing grammars with attributes allows for information flow between domain's concepts supporting features disclosing and constrains verification. The approach is validated on some simple house layout and the directions for the future development of the system are outlined. The paper focuses on conceptual framework only and, as such, is intended to stimulate further research into the various implementation considerations that are prerequisite of largescale applications.

Future directions for the introduced ideas are both theoretical and practical. The former ones include generalizing concepts to be more applicable in different domains. The later ones are intended to develop methods and tools directly applicable in design automation of architectural domain.

Fig. 1 .

 1 Fig. 1. Syntactic structuring and semantic analysis -an overall perspective.

Fig. 2 .

 2 Fig. 2. Dimensionality of gablefront house layout: an example of two story two bay house layout and its decomposition in three dimensional space Floor-Length-Bay.

Fig. 3 .

 3 Fig. 3. Part of derivation tree in the grammar shown in section 2.1. A second bay of the ground floor of the house from Figure 2 (left part of the Figure) and exemplary room without hall (right part of the Figure).

Fig. 4 .

 4 Fig. 4. Synthesized attributes (left part of the Figure) and inherited attributes (right part of the Figure).

Fig. 5 .

 5 Fig. 5. Inherited attributes controlling equality of lengths of bays.

Fig. 6 .

 6 Fig. 6. Information flow in the derivation tree of an attributive grammar: control of bays length and zones connectivity.


Dominik Żelazny
email: dominik.zelazny@pwr.wroc.pl

An evolutionary approach to cyclic real world scheduling

Keywords: flow shop problem, cyclic scheduling, real world problem, naturebased algorithm

Real world problems are often an inspiration for engineers to model and solve new scheduling problems. In this paper a cyclic scheduling of jobs with uncertain data is considered. A minimization of the cycle time represents an important economical factor considered by the companies. Proposed model was tested and data concerning processing times was obtained. Due to the nature of stations and human operator factor, we deal with uncertain data modeled using fuzzy numbers. For the modeled production station a fuzzy genetic algorithm was proposed and tested against deterministic algorithms. Proposed algorithm outperformed all deterministic algorithms.

Introduction

Maintaining competitive position in fast changing market requires companies to use new methods of optimization and drives scientists to develop more efficient algorithms. Due to that competitiveness, developing effective, advanced methods is extremely important. The so-called permutation flow shop scheduling problem (PFSP) represents a class of widely studied cases based on ideas derived from production engineering.

Most of the currently researched problems consider classic criterion and data, thus are easily adaptable to real world applications, but modern scheduling problems need more advanced models. This resulted in companies switching to cyclic scheduling models, where different products are manufactured as a Minimal Part Set -MPS.The most common optimization of such a system is minimization of the cycle time -the time between the beginning of one MPS and the beginning of the next one.

More complex models include uncertain data, which can represent systems with tasks performed by human operators or in conditions which don't guarantee deterministic processing times. Those factors add uncertain data to the analyzed systems.

In this paper a cyclic scheduling problem with uncertain data is considered. Moreover, a miniature production line (described in detail in [START_REF]Cyclic Scheduling Line with Uncertain Data[END_REF]) was used to perform tests and model the problem. Fuzzy numbers are employed to identify and model the uncertain data. A meta-heuristic algorithm was developed to obtain production schedules for proposed model. The results are compared with deterministic algorithms.

Literature overview

Here we present a brief overview of research considering cyclic job scheduling and fuzzy scheduling problems. We start with cyclic scheduling which received considerable attention. In paper [START_REF] Smutnicki | An efficient algorithm for finding minimal cycle time in cyclic job shop scheduling problem[END_REF] theoretical and numerical properties of methods for obtaining the minimal cycle time are studied. The cycle time is estimated through several expressions which are then compared based on their convergence speed. The distribution of the number of MPS needed to ascertain the cycle time is examined, with 3 to 4 MPS being enough almost 98% of the time. In paper [START_REF] Bożejko | Block approach to the cyclic flow shop scheduling[END_REF] graph model of the problem is employed to establish block elimination properties. Conducted research indicate improvement of the efficiency of the search process for cyclic flow shop problem. The solving methods using parallel computing have also appeared, for example, in paper [START_REF] Bożejko | Parallel Simulated Annealing Algorithm for Cyclic Flexible Job Shop Scheduling Problem[END_REF] two parallel techniques -vector processing and multi-walk method -were employed to solve cyclic flexible job shop scheduling problem (CFJSSP). New method of computing the cycle time was also presented.

Problem description

A miniature production line is considered (see 1). The model consists of five separate machines. The flow of every detail through the system can be divided into separate phases called stations. Station A consists of transportation module, production line (A1) and a pneumatic arm (A2), which transports the details from station A to station B. Station B consists of four steps: B1) transportation module, which is supported by a human operator, B2) lift, which transports the detail to B3) measurement station, from where detail is taken by B4) transportation module, which moves it to station C. Station C is our main station, where details are processed. First, they are transported by module C1, then they are processed on C2, transported by module C3 and processed for the second time on C4. At last, details are transported by module C5 to station D. First, details are transported using pneumatic arm (module D1) to module the inclined slope (module D2), which transports them to station E. Last station consists of two modules, first (E1) transports details to one of the three existing gates, while the second moves the detail from the gate to the chosen exit.

Mathematical model

Described system can be identified as a cyclic permutation flow shop scheduling problem (CPFSP). This is the manufacturing system with sequential structure of service stages (machines). In this system following elements are defined:

-M = 1, 2, . . . , m -set of machines, -J = 1, 2, . . . , n -set of jobs (details), -p i,j -processing time of job j on machine i, -s i,j,k -refitting time of machine i from job j to job k, -t i,j -transportation time of job j from machine i to machine i + 1, where i = 1, 2, . . . , m, j, k = 1, 2, . . . , n. In the modeled production system following processing steps are distinguished: physical measurement (step B3), first processing (step C2), second processing (step C4) and sorting of the details (steps E1 and E2). Operation processing times p i depend on the detail to be processed. Between each pair of subsequent machines i and i + 1 exists a non-zero transportation time. Refitting takes place only before first and second processing (steps C2 and C4) and depends on the details to be processed before and after the fitting.

A flow shop production system with 4 machines M = {1, 2, 3, 4} is defined. Jobs from set J , are to be processed in non-zero processing times. Set of operations is defined as O = {1, 2, . . . , 4n} and each job j consists of 4 operations (O 1,j , . . . , O 4,j ) processed on subsequent machines. Each machine can process only one job at the time and each job can be processed only at one machine at the same time. Moreover, interruption of processing of a operation is not allowed.

In cycle x all operations O for the x-th MPS must be performed. Moreover, this set can be decomposed into non-empty subsets O k , k ∈ {1, 2, . . . , m}, containing operations from one machine k.

Schedule of jobs can be defined as a permutation π = (π(1), π(2), . . . , π(n)), where π(i) is an i-th job from permutation π

Let [S x ] m×n be a matrix of starting times of jobs on x-th MPS, where S x i,j is a starting time of job j on machine i. Lets assume that the timetable of the system is fully cyclic. As such, there exists a constant T (π) called period, such as:

S x+1 i,π(j) = S x i,π(j) + T (π), (1)
where i = 1, 2, . . . , m, j = 1, 2, . . . , n and x ∈ N. Period T (π) depends on permutation π and is called cycle time. Minimal value of T (π) will be called minimal cycle time and will be denoted as T * (π). Optimizations goal is to minimize following function:

T * (π * ) = min{T * (π) : π ∈ Φ}, (2)
Without the loss of generality, we can assume that start and completion times of the first details on first machines are as follows: S 1,π(1) = 0 and C 1,π(1) = p 1,π1 . Completion times of details on the machines are calculated using the following recursive equation:

C i,π(j) = max {C i,π(j-1) + s i,π(j),π(k) , C i-1,π(j) +t i-1,π(j) } + p i,π(j) , (3)
where i = 1, . . . , m, j = 1, . . . , n and k = 1, . . . , n.

Goal is to optimize following objective function:

T (π) = max i∈M {C x i,π(n) -S x i,π(1) }. (4)
5 Uncertain data -fuzzy numbers

Fuzzy numbers [START_REF] Dubois | Operations on fuzzy numbers[END_REF] are a specific case of fuzzy sets [START_REF] Zadeh | Fuzzy sets[END_REF] -which are defined through membership function f : R → [0, 1] -and can be viewed as generalization of the real numbers. One of the most common membership functions defines fuzzy number x as a triple (a, b, c), where a, b, c ∈ R, resulting in triangular visualization.

Lets consider step B4 for some job j. The processing time of that step for job j was measured a number of times (12 in this case), creating a vector pj with 12

B 4 b = p 1,j + p 2,j + • • • + p 11,j 12 = 3.30, (5)
B 4 c = max(p 1,j , p 2,j , . . . , p 11,j ) = 7.20,

yielding B 4 = (1.20, 3.30, 7.20).

The above procedure can be applied to all steps in the production process and then be used to define all processing and transport times through fuzzy numbers. For example, transport time t 3,j is the sum of times of steps C5, D1, D2. Thus, it can be represented as a fuzzy number computed as a sum of 3 fuzzy numbers i.e. t 3,j = C 5 + D 1 + D 2 . The resulting fuzzy numbers are presented in Table 2. Transport times are identical for all jobs. Fuzzy number p i,j represents fuzzy processing time of job j on machine i. This time is dependent on the scaling parameter γ j which is different for various jobs. It is easily observed that the uncertainty in the considered system is significant, as the ratio c a can be as high as 2 or 3 for some of the presented fuzzy numbers.

Proposed method

For the purpose of this article an evolutionary method was proposed. Parameters of the algorithm were automatically adjusted (self-set parameters). Moreover, a second stop rule was implemented. When execution reaches certain (predetermined by tests) run time, the algorithm stops at current iteration.

Genetic Algorithm

Genetic Algorithm (GA) is a multi-agent method based on the evolution process found in the nature to find better solutions. Evolutionary algorithms use techniques inspired by natural occurring factors, such as inheritance, mutation, selection and crossover to generate solutions to optimization problems. Usually, the evolution starts from random initial population, which consists of individuals. In each iteration, called generation, those individuals are modified (by means of mutation and/or crossover) and their fitness is evaluated in order to select best solutions for next generation. Over the years, different approaches to the GA were proposed and tested for a variety of optimization problems. Our GA uses external Pareto archive in order to maintain non-dominated solutions through successive iterations. The individuals in population are represented by the following: jobs permutation, values of criteria functions and relative closeness indicator calculated by the TOPSIS method. Initial population includes solutions obtained from certain constructive algorithms, prepared to optimize one of the criteria. Such initialization allows faster designation of the approximation of Pareto front. Mutation is performed by interchanging two random jobs in schedule, while crossover uses a partially matched crossover (PMX) scheme. Fitness values are evaluated using the TOPSIS technique and are then used in tournament selection. After the selection, half of parent and child population is combined into new parent population. Moreover, when relative closeness values converge to zero, an anti-stagnation function is employed. Similar genetic algorithms have been proposed in [START_REF] Bożejko | Parallel packing procedure for three dimensional bin packing problem[END_REF][START_REF] Bożejko | Parallel Coevolutionary Algorithm for Three-Dimensional Bin Packing Problem[END_REF].

Computer experiment

All algorithms were implemented in C++ and compiled with Embarcadero C++ Builder XE7 Professional. The programs were tested on Intel R Core i7-3770 3400MHz machine (8 concurrent threads) with 8GB of RAM under the Microsoft Windows 8.1 64b operating system. In order to compare the results, 3 deterministic algorithms were implemented, resulting in tests of following algorithms: It can be easily observed, that fuzzy genetic algorithm (henceforth called FGA) outperformed deterministic GAs considerably. In every test, best run of the fuzzy version had best results from all of the algorithms. Its average run was better in most cases than the best runs of deterministic algorithms. Moreover, worst run of the fuzzy algorithm was better than best runs of D MIN and D MAX algorithms and, in some cases, D MID deterministic algorithm.

There are 8 groups of 5 instances each, yielding 40 instances of problems for proposed problem. Groups are dependant on the number of jobs to be performed, starting from 10 up to 45. Proposed algorithm, as well as deterministic versions of GA, were tested 10 times per instance. The summarized results of first 4 groups are shown in Tab. 3 and last 4 groups in Tab.4.

Conclusions and further research

In this paper a fuzzy genetic algorithm for a real world model of cyclic scheduling problem was proposed. The mathematical model of the problem was based on the cyclic flow shop scheduling system with uncertain (fuzzy) data. Algorithms, fuzzy and deterministic, were tested using instances with number of jobs ranging from 10 to 45. The results indicate that the proposed FGA significantly outperforms the deterministic algorithms. Each algorithm was tested under the same test conditions (maximal worktime and maximal number of iterations), so that the results were not affected by differences in test procedure.

Fig. 1 .

 1 Fig. 1. Model of a production line

1 .

 1 F -fuzzy algorithm. Based on the fuzzy problem instances with times in the form of fuzzy numbers e.g. {a, b, c}. 2. D MIN -deterministic algorithm working on real numbers. Numbers are generated from the fuzzy instance using a value of fuzzy number. 3. D MID -deterministic algorithm. Numbers are generated from the fuzzy instance using b value of fuzzy number. 4. D MAX -deterministic algorithm. Numbers are generated from the fuzzy instance using c value of fuzzy number

Table 1 .

 1 Results of measurement of p for step B4 (in seconds)

	p1,j p2,j	p3,j	p4,j	p5,j	p6,j	p7,j	p8,j	p9,j	p10,j	p11,j	p12,j
	1.48 7.20 4.72 1.56 1.20 6.24 2.92 4.76 1.68	2.64	2.48	2.72

Table 2 .

 2 Fuzzy numbers obtained for the proposed production system

	Fuzzy number	a	b	c
	C 5	3.44	3.44	3.45
	D 1	17.52	27.20	47.52
	D 2	0.69	1.51	2.92
	t0,j	13.76	17.61	24.44
	t1,j	4.64	6.75	10.65
	t2,j	3.44	3.44	3.45
	t3,j	21.65	32.15	53.89
	p1,j	2.32 • γj	2.79 • γj	3.44 • γj
	p2,j	1.40 + αj	1.40 + αj	1.40 + αj
	p3,j	1.40 + βj	1.40 + βj	1.40 + βj
	p A 4,j	1.40	2.71	5.04
	p B 4,j	2.44	4.03	7.32
	p C 4,j	3.32	4.36	7.84
	elements as shown in Table 1. The estimated processing time for step B4 can be
	now modeled using fuzzy number B 4 = (B 4 a , B 4 b , B 4 c ) as follows:
	B 4

a = min(p 1,j , p 2,j , . . . , p 11,j ) = 1.20,

Table 3 .

 3 Summary of results, instance sizes 10-25

	Instance	Algorithm	Best run [%]	Average run [%]	Worst run [%]
	10	F	100,00	113,91	144,43
		DMIN	220,51	256,44	306,31
		DMID	200,64	234,50	283,59
		DMAX	202,76	234,76	278,15
	15	F	100,00	113,14	148,71
		DMIN	256,75	298,16	354,26
		DMID	188,42	219,84	266,55
		DMAX	213,44	244,54	289,41
	20	F	100,00	114,58	139,31
		DMIN	284,74	315,46	357,21
		DMID	185,23	212,78	247,60
		DMAX	211,88	241,71	278,66
	25	F	100,00	124,36	155,24
		DMIN	280,57	311,85	351,78
		DMID	203,25	228,54	261,83
		DMAX	215,68	244,37	280,67

Table 4 .

 4 Summary of results, instance sizes 30-45

	Instance	Algorithm	Best run	Average run	Worst run
	30	F	100,00	136,01	182,08
		DMIN	348,17	386,79	437,72
		DMID	201,77	232,37	270,41
		DMAX	272,22	308,10	354,31
	35	F	100,00	149,14	204,07
		DMIN	352,34	388,99	437,76
		DMID	138,15	177,69	227,37
		DMAX	252,77	289,37	332,77
	40	F	100,00	128,40	174,28
		DMIN	346,05	381,01	425,99
		DMID	115,62	146,73	190,44
		DMAX	220,48	262,26	311,40
	45	F	100,00	117,05	144,44
		DMIN	276,09	297,31	325,59
		DMID	105,11	129,60	156,19
		DMAX	199,96	217,35	240,55

Acknowledgements

This work is co-financed by the M loda Kadra project, B50304.